﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<math.h>
//////#include<iostream>
//////using namespace std;
//////#include<stdlib.h>
//////#include<vector>
//////#include<algorithm>
//////
//////int cmp(int x, int y)
//////{
//////    return x > y;
//////}
//////int main()
//////{
//////    int n = 0;
//////    cin >> n;
//////
//////    int* arr = new int[n];
//////
//////    for (int i = 0; i < n; i++)
//////    {
//////        cin >> arr[i];
//////    }
//////    vector<int> v;
//////    for (int i = 0; i < n; i++)
//////    {
//////        v.push_back(arr[i]);
//////    }
//////    sort(v.begin(), v.end());
//////    int cur = 1;
//////    int prev = 0;
//////    int sum = 0;
//////
//////    while (cur < n)
//////    {
//////        int left = prev;
//////        int right = left;
//////        if (v[prev] == v[cur])
//////        {
//////            while (right < n && v[left] == v[right])
//////            {
//////                right++;
//////            }
//////            int num = right - left;
//////            sum += (num * (num - 1)) / 2;
//////            prev = right;
//////            cur = prev + 1;
//////            continue;
//////        }
//////        prev++;
//////        cur++;
//////    }
//////    int count = n * (n - 1) / 2;
//////    sum = count - sum;
//////    cout << sum;
//////
//////    return 0;
//////}
//////
//////#include<iostream>
//////using namespace std;
//////#include<stdlib.h>
//////
//////
//////#define N 4
//////
//////#define Y(n) ((N+2)*n)
//////
//////struct Add
//////{
//////	char a;
//////	int b;
//////};
//////
//////int main() 
//////{
//////	int z = 0;
//////
//////	z = 2 * (N + Y(5 + 1));
//////
//////	cout << z << endl;
//////	return 0;
//////}
//////
//////#include <iostream>
//////using namespace std;
//////#include<string>
//////#include<map>
//////struct Compare
//////{
//////    bool operator()(pair<string, int> kv1, pair<string, int> kv2)
//////    {
//////        return (kv1.second > kv2.second) || ((kv1.second == kv2.second) && (kv1.first < kv2.first));
//////    }
//////};
//////
//////int main()
//////{
//////    map<string, int, Compare> mp;
//////    string str;
//////    while (cin >> str)
//////    {
//////        if (str.back() == '.')
//////        {
//////            str.pop_back();
//////        }
//////        //
//////        mp[str]++;//方括号， 如果不存在就插入， 如果存在就返回val。它的返回值
//////    }
//////    //计算完之后， 
//////
//////
//////}
//////// 64 位输出请用 printf("%lld")
////
////
////
//////#include<algorithm>
//////#include<iostream>
//////using namespace std;
//////namespace cws 
//////{
//////	template<class K>
//////	class BinaryTreeNode 
//////	{
//////	public:
//////		BinaryTreeNode* _left;
//////		BinaryTreeNode* _right;
//////		K _key;
//////
//////		BinaryTreeNode(const K& val) 
//////			:_key(val)
//////			,_left(nullptr)
//////			,_right(nullptr)
//////		{}
//////	};
//////
//////
//////
//////
//////	template<class K>
//////	class BSTree 
//////	{
//////	public:
//////		typedef BinaryTreeNode<K> node;
//////		BSTree() 
//////			:_root(nullptr)
//////		{}
//////
//////		BSTree(const BSTree<K>& bt) 
//////		{
//////			_root = _BSTree(bt._root);
//////		}
//////
//////		BSTree<K>& operator=(BSTree<K> bt)
//////		{
//////			swap(_root, bt._root);
//////			return *this;
//////		}
//////		
//////		~BSTree() 
//////		{
//////			_Destory(_root);
//////		}
//////
//////		bool Insert(const K& key) 
//////		{
//////			if (_root == nullptr) 
//////			{
//////				_root = new node(key);
//////				return true;
//////			}
//////			//
//////			node* parent = _root;
//////			node* cur = _root;
//////			while (cur != nullptr) 
//////			{
//////				if (key > cur->_key) 
//////				{
//////					parent = cur;
//////					cur = cur->_right;
//////				}
//////				else if (key < cur->_key) 
//////				{
//////					parent = cur;
//////					cur = cur->_left;
//////				}
//////				else 
//////				{
//////					return false;
//////				}
//////
//////			}
//////			if (key < parent->_key) 
//////			{
//////				parent->_left = new node(key);
//////			}
//////			else 
//////			{
//////				parent->_right = new node(key);
//////			}
//////			return true;
//////
//////		}
//////
//////
//////		node* Find(const K& key) 
//////		{
//////			node* cur = _root;
//////			while (cur != nullptr) 
//////			{
//////				if (key > cur->_key) 
//////				{
//////					cur = cur->_right;
//////
//////				}
//////
//////				else if (key < cur->_key) 
//////				{
//////					cur = cur->_left;
//////				}
//////				else 
//////				{
//////					return cur;
//////				}
//////			}
//////
//////
//////			return nullptr;
//////		}
//////
//////		bool Erase(const K& key)
//////		{
//////			node* parent = _root;
//////			node* cur = _root;
//////			while (cur != nullptr)
//////			{
//////				if (key > cur->_key)
//////				{
//////					parent = cur;
//////					cur = cur->_right;
//////				}
//////				else if (key < cur->_key)
//////				{
//////					parent = cur;
//////					cur = cur->_left;
//////				}
//////				else 
//////				{
//////					//找到了， 开始删除
//////
//////					if (cur->_left == nullptr) 
//////					{
//////						if (cur == _root) 
//////						{
//////							_root = _root->_right;
//////							delete cur;
//////							cur = nullptr;
//////							return true;
//////						}
//////						if (parent->_left == cur) 
//////						{
//////							parent->_left = cur->_right;
//////						}
//////						else 
//////						{
//////							parent->_right = cur->_right;
//////						}
//////						delete cur;
//////					}
//////					else if (cur->_right == nullptr)
//////					{
//////						if (_root == cur) 
//////						{
//////							_root = _root->_left;
//////							delete cur;
//////							cur = nullptr;
//////							return true;
//////						}
//////						if (parent->_left == cur)
//////						{
//////							parent->_left = cur->_left;
//////						}
//////						else 
//////						{
//////							parent->_right = cur->_left;
//////						}
//////						delete cur;
//////					}
//////					else 
//////					{
//////						//这种情况下， 左右孩子都有。就需要进行判断。 
//////						node* max_left = cur->_left;
//////						node* pmax_left = cur;
//////						
//////						while (max_left->_right != nullptr) 
//////						{
//////							pmax_left = max_left;
//////							max_left = max_left->_right;
//////						}
//////						cur->_key = max_left->_key;
//////						if (pmax_left == cur)
//////						{
//////							pmax_left->_left = max_left->_left;
//////
//////						}
//////						else 
//////						{
//////							pmax_left->_right = max_left->_left;
//////						}
//////
//////						delete max_left;
//////					}
//////
//////					return true;
//////				}
//////
//////			}//end of while
//////			return false;
//////		}
//////
//////		void InOrder() 
//////		{
//////			_InOrder(_root);
//////		}
//////
//////		node* FindR(const K& key) 
//////		{
//////			return _FindR(_root, key);
//////		}
//////
//////
//////		bool InsertR(const K& key) 
//////		{
//////			return _InsertR(_root, key);
//////		}
//////
//////		bool EraseR(const K& key) 
//////		{
//////			return _EraseR(_root, key);
//////		}
//////
//////
//////		
//////
//////	protected:
//////
//////		bool _EraseR(node*& root, const K& key) 
//////		{
//////			if (key > root->_key) 
//////			{
//////				return _EraseR(root->_right, key);
//////			}
//////			else if (key < root->_key) 
//////			{
//////				return _EraseR(root->_left, key);
//////			}
//////			else 
//////			{
//////				//找到了
//////
//////				node* cur = root;
//////				if (root->_left == nullptr) 
//////				{
//////					root = root->_right;
//////					delete cur;
//////					return true;
//////				}
//////				else if (root->_right == nullptr) 
//////				{
//////					root = root->_left;
//////					delete cur;
//////					return true;
//////				}
//////				else 
//////				{
//////					node* max_left = root->_left;
//////					while (max_left->_right != nullptr) 
//////					{
//////						max_left = max_left->_right;
//////					}
//////
//////					swap(max_left->_key, root->_key);
//////					return _EraseR(root, key);
//////				}
//////			}
//////
//////		}
//////
//////		bool _InsertR(node*& root, const K& key) 
//////		{
//////			if (root == nullptr) 
//////			{
//////				root = new node(key);
//////				return true;
//////
//////			}
//////
//////			if (key > root->_key) 
//////			{
//////				_InsertR(root->_right, key);
//////			}
//////			else if (key < root->_key) 
//////			{
//////				_InsertR(root->_left, key);
//////			}
//////			else 
//////			{
//////				return false;
//////			}
//////		}
//////
//////
//////		node* _FindR(node* root, const K& key) 
//////		{	
//////			if (root == nullptr) 
//////			{
//////				return nullptr;
//////			}
//////			if (root->_key == key) 
//////			{
//////				return root;
//////			}
//////			else
//////			{
//////				node* left = _FindR(root->_left, key);
//////				node* right = _FindR(root->_right, key);
//////				if (left != nullptr)
//////				{
//////					return left;
//////				}
//////				else if (right != nullptr)
//////				{
//////					return right;
//////				}
//////				else 
//////				{
//////					return nullptr;
//////				}
//////
//////			}
//////		}
//////
//////
//////		void _InOrder(node* root) 
//////		{
//////			if (root == nullptr) 
//////			{
//////				return;
//////			}
//////			_InOrder(root->_left);
//////			cout << root->_key << " ";
//////			_InOrder(root->_right);
//////		}
//////
//////		node* _BSTree(const node* rootCopy) 
//////		{
//////			if (rootCopy == nullptr) 
//////			{
//////				return nullptr;
//////			}
//////			//
//////			node* cur = new node(rootCopy->_key);
//////			cur->_left = _BSTree(rootCopy->_left);
//////			cur->_right = _BSTree(rootCopy->_right);
//////			return cur;
//////		}
//////
//////		void _Destory(node* root) 
//////		{
//////			if (root == nullptr) 
//////			{
//////				return;
//////			}
//////			//
//////			_Destory(root->_left);
//////			_Destory(root->_right);
//////			delete root;
//////		}
//////
//////	private:
//////		node* _root;
//////	};
//////	
//////
//////}
//////
//////
//////void testTree() 
//////{
//////	cws::BSTree<int> st, st2;
//////	st.Insert(8);
//////	st.Insert(3);
//////	st.Insert(5);
//////	st.Insert(7);
//////	st.Insert(465);
//////	st.Insert(998);
//////	st.Insert(34);
//////
//////	st2 = st;
//////
//////	st.EraseR(st.FindR(5)->_key);
//////
//////
//////
//////	st.InOrder();
//////	cout << endl;
//////	st2.InOrder();
//////
//////}
//////
//////
//////int main() 
//////{
//////
//////	testTree();
//////
//////
//////	return 0;
//////}
////
////
////#include<iostream>
////using namespace std;
////#include<algorithm>
////
////namespace cws 
////{
////	template<class K>
////	class BSTreeNode 
////	{
////	public:
////		BSTreeNode* _left;
////		BSTreeNode* _right;
////		K _data;
////
////		BSTreeNode(const K& data) 
////			:_data(data)
////			,_left(nullptr)
////			,_right(nullptr)
////		{}
////	};
////
////
////
////	template<class K>
////	class BSTree 
////	{
////	public:
////		typedef BSTreeNode<K> node;
////
////		BSTree() 
////			:_root(nullptr)
////		{}
////
////		BSTree(const BSTree& bt) 
////		{
////			_root = _BSTree(bt._root);
////		}
////
////		~BSTree() 
////		{
////			if (_root == nullptr) 
////			{
////				return;
////			}
////			_destroy(_root);
////		}
////		
////		BSTree<K>& operator=(BSTree<K> bt) 
////		{
////			swap(bt._root, _root);
////			return *this;
////		}
////
////
////
////		bool insert(const K& val) 
////		{
////			if (_root == nullptr) 
////			{
////				_root = new node(val);
////				return true;
////			}
////			//
////			node* parent = nullptr;
////			node* cur = _root;
////			while (cur != nullptr) 
////			{
////				if (val > cur->_data) 
////				{
////					parent = cur;
////					cur = cur->_right;
////				}
////				else if (val < cur->_data) 
////				{
////					parent = cur;
////					cur = cur->_left;
////				}
////				else 
////				{
////					return false;
////				}
////			}
////			//找到位置了。
////			cur = new node(val);
////			if (val > parent->_data) 
////			{
////				parent->_right = cur;
////			}
////			else 
////			{
////				parent->_left = cur;
////			}
////
////			return true;
////		}
////
////		//
////		bool erase(const K& val) 
////		{
////			node* cur = _root;
////			node* parent = nullptr;
////			while (cur != nullptr) 
////			{
////				if (val > cur->_data) 
////				{
////					parent = cur;
////					cur = cur->_right;
////				}
////				else if (val < cur->_data) 
////				{
////					parent = cur;
////					cur = cur->_left;
////				}
////				else 
////				{
////					//找到了， 开始删除.
////					//分三种情况， 一种是找到的节点为叶子节点。 还有一种情况是找到的节点其中有一个孩子为空节点。最后一种情况是两个孩子都存在。
////					//还有一种极为特殊的情况， 删除的节点是根节点， 这个时候应该直接进行托管。
////					if (cur->_left == nullptr) 
////					{
////						if (cur == _root) 
////						{
////							_root = cur->_right;
////							delete cur;
////							cur = nullptr;
////							return true;
////						}
////						//
////						if (cur == parent->_left) 
////						{
////							parent->_left = cur->_right;
////						}
////						else 
////						{
////							parent->_right = cur->_right;
////						}
////						delete cur;
////						return true;
////					}
////					else if (cur->_right == nullptr) 
////					{
////						if (cur == _root) 
////						{
////							_root = cur->_left;
////							delete cur;
////							cur = nullptr;
////							return true;
////						}
////						//
////						if (cur == parent->_left) 
////						{
////							parent->_left = cur->_left;
////						}
////						else
////						{
////							parent->_right = cur->_left;
////						}
////						delete cur;
////						return true;
////					}
////					else 
////					{
////						//左右孩子都存在
////						node* left_max = cur->_left;
////						node* pleft_max = cur;
////						while (left_max->_right != nullptr) 
////						{
////							pleft_max = left_max;
////							left_max = left_max->_right;
////						}
////						//找到最大值。
////						swap(cur->_data, left_max->_data);
////
////						if (pleft_max == cur) 
////						{
////							pleft_max->_left = left_max->_left;
////						}
////						else 
////						{
////							pleft_max->_right = left_max->_left;
////						}
////
////						delete left_max;
////						return true;
////					}
////				}
////			}
////
////		}
////
////		//Find
////		node* Find(const K& val) 
////		{
////			node* cur = _root;
////			while (cur != nullptr) 
////			{
////				if (val > cur->_data)
////				{
////					cur = cur->_right;
////				}
////				else if (val < cur->_data)
////				{
////					cur = cur->_left;
////				}
////				else
////				{
////					return cur;
////				}
////			}
////			return nullptr;
////		}
////
////
////
////
////		void InOrder() 
////		{
////			_InOrder(_root);
////		}
////		void _destroy(node*& root)
////		{
////			if (root == nullptr) 
////			{
////				return;
////			}
////			if (root->_left == nullptr && root->_right == nullptr)
////			{
////				node* cur = root;
////				root = nullptr;
////				delete cur;
////				return;
////			}
////			//
////			if (root->_left != nullptr) 
////			{
////				_destroy(root->_left);
////
////			}
////			else if (root->_right != nullptr)
////			{
////				_destroy(root->_right);
////
////			}
////
////		}
////	protected:
////
////	
////
////		node* _BSTree(node* root) //搜索树后序遍历创建节点。
////		{
////			if (root == nullptr) 
////			{
////				return nullptr;
////			}
////			//
////			node* cur = new node(root->_data);
////			cur->_left = _BSTree(root->_left);
////			cur->_right = _BSTree(root->_right);
////
////			return cur;
////		}
////
////		void _InOrder(const node* root) 
////		{
////			if (root == nullptr)
////			{
////				return;
////			}
////			_InOrder(root->_left);
////			cout << root->_data << " ";
////			_InOrder(root->_right);
////		}
////
////	public:
////		node* _root;
////	};
////}
////
////int main() 
////{
////	cws::BSTree<int> bt;
////	bt.insert(8);
////	bt.insert(8);
////	bt.insert(2);
////	bt.insert(434);
////	bt.insert(8);
////	bt.insert(3);
////	bt.insert(4);
////	bt.insert(7);
////	bt.InOrder();
////	cout << endl;
////	bt.erase(8);
////	bt.erase(3);
////	cws::BSTree<int> bt2;
////	bt2 = bt;
////	bt.InOrder();
////
////
////
////	return 0;
////}
//
//#include<iostream>
//using namespace std;
//
//#include<algorithm>
//#include<assert.h>
//
//
//namespace cws
//{
//	template<class K, class V>
//	class AVLTreeNode 
//	{
//	public:
//		AVLTreeNode* _left;
//		AVLTreeNode* _right;
//		AVLTreeNode* _parent;
//		pair<K, V> _kv;
//		int _bf;	
//
//		AVLTreeNode(const pair<K, V>& kv = pair<K, V>()) 
//			:_kv(kv)
//			,_left(nullptr)
//			,_right(nullptr)
//			,_parent(nullptr)
//			,_bf(0)
//		{}
//	};
//
//	template<class K, class V> 
//	class AVLTree 
//	{
//	public:
//		typedef AVLTreeNode<K, V> node;
//		typedef AVLTree<K, V> tree;
//
//
//		// ///////////////////////////////////Conductor
//		AVLTree() 
//			:_root(nullptr)
//		{}
//
//		AVLTree(const AVLTree<K, V>& bt) 
//		{
//			_root = _AVLTree(bt._root);
//		}
//		
//		~AVLTree() 
//		{
//			if (_root == nullptr) 
//			{
//				return;
//			}
//			//
//			_destory(_root);
//		}
//		tree& operator=(tree bt) 
//		{
//			swap(_root, bt._root);
//			return *this;
//		}
//
//		///////////////////////////////////////
//
//		bool insert(const pair<K, V>& kv) 
//		{
//			node* parent = nullptr;
//			node* cur = _root;
//			if (_root == nullptr) 
//			{
//				_root = new node(kv);
//				return true;
//			}
//			//
//			while (cur != nullptr) 
//			{
//				if (kv > cur->_kv) 
//				{
//					parent = cur;
//					cur = cur->_right;
//				}
//				else if (kv < cur->_kv) 
//				{
//					parent = cur;
//					cur = cur->_left;
//				}
//				else 
//				{
//					//出现问题. 相同数值的节点插入。 
//					return false;
//				}
//			}
//			//到了空节点。
//			cur = new node(kv);
//			if (kv > parent->_kv) 
//			{
//				parent->_right = cur;
//			}
//			else 
//			{
//				parent->_left = cur;
//			}
//			//
//
//			while (parent) 
//			{
//				if (cur == parent->_left) 
//				{
//					parent->_bf--;
//				}
//				else if (cur == parent->_right) 
//				{
//					parent->_bf++;
//				}
//				//
//				if (parent->_bf == 1 || parent->_bf == -1) 
//				{
//					cur = parent;
//					parent = parent->_parent;
//				}
//				else if (parent->_bf == 0) 
//				{
//					break;
//				}
//				else if (parent->_bf == 2 || parent->_bf ==  -2)
//				{
//					//需要进行旋转处理
//					if (parent->_bf == 2 && cur->_bf == 1) 
//					{
//						//右右， 以父亲节点为基准进行左旋
//						RotateL(parent);
//					}
//					else if (parent->_bf == 2 && cur->_bf == -1) 
//					{
//						//右左， 以右孩子为基准进行右旋， 再以父亲节点为基准进行左旋
//						RotateR(cur);
//						RotateL(parent);
//					}
//					else if (parent->_bf == -2 && cur->_bf == 1) 
//					{
//						//左右， 以左孩子节点为基准进行左旋， 再以父亲节点为基准进行右旋
//						RotateL(cur);
//						RotateR(parent);
//
//					}
//					else if (parent->_bf == -2 && cur->_bf == -1) 
//					{
//						//左左， 以父亲节点为基准右旋
//						RotateR(parent);
//					}
//
//				}
//				else 
//				{
//					assert(false);
//				}
//
//
//			}//end of while 
//
//
//		}
//
//
//		void InOrder() 
//		{
//			_InOrder(_root);
//		}
//
//
//		bool IsAVLTree()
//		{
//			return _IsAVLTree(_root);
//		}
//		
//
//
//	protected:
//
//		bool _IsAVLTree(node* root) 
//		{
//			if (root == nullptr) 
//			{
//				return true;
//			}
//			//
//			if (root->_bf >= 2) 
//			{
//				cout << "节点的平衡因子大于1" << endl;
//				return false;
//			}
//
//			return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
//		}
//
//		void _InOrder(node* root) 
//		{
//			if (root == nullptr) 
//			{
//				return;
//			}
//			//
//			_InOrder(root->_left);
//			cout << root->_kv.first << " ";
//			_InOrder(root->_right);
//		}
//
//		//旋转的规则， 保持他继续是一棵搜索树。 
//		//旋转的目的， 更新平衡因子， 降低整棵树的高度。 
//		void RotateL(node* parent) 
//		{
//			node* subR = parent->_right;
//			node* subRL = subR->_left;
//			
//			parent->_right = subRL;
//			if (subRL != nullptr) 
//			{
//				subRL->_parent = parent;
//			}
//			//
//			node* ppnode = parent->_parent;
//			parent->_parent = subR;
//			subR->_left = parent;
//			if (ppnode == nullptr) 
//			{
//				subR->_parent = ppnode;
//				_root = subR;
//			}
//			else 
//			{
//				if (parent == ppnode->_left) 
//				{
//					subR = ppnode->_left;
//					subR->_parent = ppnode;
//				}
//				else 
//				{
//					subR = ppnode->_right;
//					subR->_parent = ppnode;
//				}
//			}
//
//			parent->_bf = subR->_bf = 0;
//
//		}
//
//		void RotateR(node* parent) 
//		{
//			node* subL = parent->_left;
//			node* subLR = subL->_right;
//			//
//			parent->_left = subLR;
//			if (subLR != nullptr) 
//			{
//				parent->_left = subLR;
//			}
//
//			node* ppnode = parent->_parent;
//			parent->_parent = subL;
//			subL->_right = parent;
//			if (ppnode == nullptr) 
//			{
//				subL->_parent = ppnode;
//				_root = subL;
//			}
//			else 
//			{
//				if (ppnode->_left == parent) 
//				{
//					ppnode->_left = subL;
//					subL->_parent = ppnode;
//				}
//				else 
//				{
//					ppnode->_right = subL;
//					subL->_parent = ppnode;
//				}
//
//			}
//
//			parent->_bf = subL->_bf = 0;
//
//		}
//
//
//		void RotateLR(node* parent) 
//		{
//			node* subL = parent->_left;
//			node* subLR = subL->_right;
//			int bf = subLR->_bf;
//			RotateL(subL);
//			RotateR(parent);
//			if (bf == 1) 
//			{
//				subL->_bf = -1;
//				parent->_bf = 0;
//				subLR->_bf = 0;
//			}
//			else if (bf == -1) 
//			{
//				subL->_bf = 0;
//				parent->_bf = 1;
//				subLR->_bf = 0;
//			}
//			else 
//			{
//				subL->_bf = parent->_bf = subLR->_bf = 0;
//			}
//		}
//
//		void RotateRL(node* parent)
//		{
//			node* subR = parent->_right;
//			node* subRL = subR->_left;
//			int bf = subRL->_bf;
//			RotateR(subR);
//			RotateL(parent);
//
//			if (bf == 1)
//			{
//				subRL->_bf = 0;
//				subR->_bf = 0;
//				parent->_bf = -1;
//			}
//			else if (bf == -1) 
//			{
//				subRL->_bf = 0;
//				subR->_bf = 1;
//				parent->_bf = 0;
//			}
//			else 
//			{
//				subRL->_bf = subR->_bf = parent->_bf = 0;
//			}
//
//		}
//
//
//		void _destory(node*& root) 
//		{
//			if (root->_left == nullptr && root->_right == nullptr) 
//			{
//				node* cur = root;
//				root = nullptr;
//				delete cur;
//				return;
//			}
//			//
//			if (root->_left != nullptr) 
//			{
//				_destory(root->_left);
//			}
//			else if (root->_right != nullptr) 
//			{
//				_destory(root->_right);
//			}
//			
//		}
//
//		node* _AVLTree(node* root) 
//		{
//			if (root == nullptr) 
//			{
//				return nullptr;
//			}
//			//
//			node* cur = new node(root->_kv);
//			_AVLTree(root->_left);
//			_AVLTree(root->_right);
//			return cur;
//		}
//
//	private:
//		node* _root;
//
//	};
//
//
//}
//
//int main() 
//{
//	cws::AVLTree<int, int> bt;
//	bt.insert(make_pair(1, 1));
//	bt.insert(make_pair(34, 1));
//	bt.insert(make_pair(3, 1));
//	bt.insert(make_pair(3, 1));
//	bt.insert(make_pair(7, 1));
//	bt.insert(make_pair(6, 1));
//
//	bt.InOrder();
//	cout << endl;
//	bt.IsAVLTree();
//
//	return 0;
//}


//#include<iostream>
//using namespace std;
//#include"RBTree.h"
//
//int main() 
//{
//	cws::RBTree<int, int> bt;
//	bt.insert(make_pair(9, 2));
//	bt.IsRBTree();
//	cout << endl;
//
//	bt.insert(make_pair(23, 2));
//	bt.IsRBTree();
//	cout << endl;
//	bt.insert(make_pair(1, 2));
//	bt.insert(make_pair(23, 2));
//	bt.insert(make_pair(1, 2));
//	bt.insert(make_pair(8, 2));
//	bt.IsRBTree();
//	cout << endl;
//	bt.insert(make_pair(34, 2));
//
//	bt.insert(make_pair(545, 2));
//
//	bt.InOrder();
//	cout << endl;
//	bt.IsRBTree();
//
//	return 0;
//}


//
//int main() 
//{
//	cws::RBTree<pair<int, int>> bt;
//	bt.insert(make_pair(1, 2));
//	bt.insert(make_pair(54, 2));
//	bt.insert(make_pair(5, 2));
//	bt.insert(make_pair(8, 2));
//	bt.insert(make_pair(878, 2));
//	bt.insert(make_pair(23432, 2));
//	bt.insert(make_pair(34, 2));
//
//	bt.InOrder();
//	cout << endl;
//	cout << bt.IsRBTree() << endl;;
//	
//	cout << bt.get_left()->_data.first << endl;
//	cout << bt.get_right()->_data.first << endl;
//
//	auto it = bt.begin();
//	while (it != bt.end()) 
//	{
//		cout << (*it).first << " ";
//		++it;
//	}
//	cout << endl;
//	auto it2 = bt.end();
//	while (it2 != bt.begin()) 
//	{
//		--it2;
//		cout << (*it2).first << " ";
//	}
//	cout << endl;
//	return 0;
//}
//
//#include"set.h"
//int main() 
//{
//	cws_set::set<int> st;
//	st.insert(1);
//	st.insert(2);
//	st.insert(9);
//	st.insert(2);
//	st.insert(6);
//	st.insert(5);
//
//	auto it = st.begin();
//	while (it != st.end()) 
//	{
//		cout << *it << endl;
//		++it;
//	}
//
//	return 0;
//}
//
//#include<iostream>
//using namespace std;
//#include"RBTree.h"
//#include"map.h"
//
//
//int main() 
//{
//	cws_map::map<int, int> mp;
//	mp.insert(make_pair(1, 2));
//	mp.insert(make_pair(5, 2));
//	mp.insert(make_pair(8, 2));
//	mp.insert(make_pair(2, 2));
//	mp.insert(make_pair(1, 2));
//	mp.insert(make_pair(3, 2));
//	mp.insert(make_pair(4, 2));
//
//	auto it = mp.begin();
//	while (it != mp.end()) 
//	{
//		cout << (*it).first << " ";
//		++it;
//	}
//	cout << endl;
//	for (auto& e : mp) 
//	{
//		cout << e.first << " ";
//	}
//	cout << endl;
//
//	return 0;
//}
//
//#include<iostream>
//#include<vector>
//using namespace std;
//
//
//namespace OpenAdress
//{
//	enum State 
//	{
//		EMPTY,
//		EXIST,
//		DELETE
//	};
//	template<class K, class V>
//	struct HashData 
//	{
//		pair<K, V> _kv;
//		State _state;
//
//		HashData()
//			:_state(EMPTY)
//		{}
//	};
//
//	template<class K, class V>
//	class HashTable 
//	{
//	public:
//		
//		void insert(const pair<K, V>& kv) 
//		{
//			//扩容处理， 哈希表开放定址法的扩容规则是那个负载因子。 负载因子应该处于0.7~0.8之间。 只要超过了这个范围， 就要进行扩容。 
//			//对于开放定址法来说， 负载因子越大， 越容易发生踩踏， 哈希表的插入效率也就越低。
//			if ((_tables.size() == 0) || ((_n * 10) / _tables.size() > 7)) 
//			{
//				int newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
//
//				//进行扩容,这里扩容的方法是重新开一片空间然后为数据重新映射位置。 
//				HashTable<K, V> newt;
//				newt._tables.resize(newsize);
//				//遍历旧表，重新映射到新表
//				for (auto& e : _tables) 
//				{
//					if (e._state == EXIST) 
//					{
//						newt.insert(e._kv);
//					}
//				}
//				_tables.swap(newt._tables);
//			}
//
//			int hashi = kv.first % _tables.size();//这里使用size（）取模， 因为对于哈希表来说， 真正有用的就是这个size（）， capacity用不到
//			int i = 1;
//			int index = hashi;
//
//			while (_tables[index]._state == EXIST) 
//			{
//				index = hashi + i;
//				index %= _tables.size();
//				i++;
//			}
//			_tables[index]._kv = kv;
//			_tables[index]._state = EXIST;
//			_n++;
//		}
//
//
//		HashData<K,V>*  Find(const K& key)
//		{
//			if (_tables.size() == 0) 
//			{
//				return nullptr;
//			}
//
//			int hashi = key % _tables.size();
//
//			int i = 1;
//			int index = hashi;
//
//			while (_tables[index]._state == EXIST) 
//			{
//				if (_tables[index]._kv.first == key) 
//				{
//					return &_tables[index];
//				}
//				else 
//				{
//					index = hashi + i;
//					index %= _tables.size();
//					i++;
//				}
//
//				if (index == hashi) 
//				{
//					return nullptr;//已经查找一圈， 直接返回空
//				}
//
//
//			}
//
//			return index;
//		}
//
//		bool Erase(const pair<K, V>& kv) 
//		{
//			HashData<K, V>* ret = Find(kv.first);
//			if (ret == -1) 
//			{
//				cout << "找不到，删除失败" << endl;
//				return false;
//			}
//			else 
//			{
//				ret->_state = DELETE;
//				_n--;
//				cout << "删除成功" << endl;
//				return true;
//			}
//
//		}
//
//
//	private:
//		vector<HashData<K, V>> _tables;
//		int _n;//存储的数据个数.
//	};
//
//}

//
//namespace HashBuget 
//{
//	template<class K, class V>
//	class HashData 
//	{
//		HashData<K, V>* _next;
//		pair<K, V> _kv;
//	};
//
//	template<class K, class V>
//	class HashTable 
//	{
//	public:
//		typedef HashData<K, V> node;
//
//		bool insert(const pair<K, V>& kv) 
//		{
//			//先进行冗余的判断操作
//			if (Find(kv.first) != nullptr) 
//			{
//				return false;
//			}//只有空才会进行插入操作。
//
//			//判断负载因子:
//			if (_n == _tables.size()) //扩容操作
//			{
//				size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
//				vector<node*> _newtables(newsize, nullptr);
//				for (auto& cur : _tables) 
//				{
//					while (cur != nullptr)//取到_tables中的元素， 然后根据这个元素的值在_tables中寻找相应的位置。 
//					{
//						node* next = cur->_next;
//
//						int newhashi = cur->_kv.first % _newtables.size();
//						cur->_next = _newtables[newhashi];
//						_newtables[newhashi] = cur;//将待处理节点给给新哈希表的对应链表之中
//						cur = next;
//					}
//				}//全部结束之后， 就将两个顺序表的三个指针交换一下。 _tables重新维护新的空间。
//				_tables.swap(_newtables);
//			}
//
//
//			int hashi = kv.first % _tables.size();
//			node* newnode = new node(kv);
//			newnode->_next = _tables[hashi];
//			_tables[hashi] = newnode;
//			_n++;
//			return true;
//		}
//
//		// 查找操作
//		node* Find(const K& key) 
//		{
//			int hashi = key % _tables.size();//先取模， 定位查找的链表位置。 
//			node* cur = _tables[hashi];//找到链表的头节点。 
//			
//			while (cur != nullptr) 
//			{
//				//只要没有到达链表的空节点， 就进行判断， 只要值相等就return， 全部检查完毕之后没有返回， 说明找不到。 返回false;
//				if (cur->_kv.first == key) 
//				{
//					return cur;
//				}
//				else 
//				{
//					cur = cur->_next;
//				}
//			}
//			return nullptr;//返回空指针代表找不到。
//		}
//
//		//删除
//		bool Erase(const K& key) 
//		{
//			//注意， 删除的操作不能使用find， 因为find直接找到了要删除的节点。 但是我们进行删除的时候没有前置节点的指针进行维护。 所以删除不了。 所以必须自己寻找
//			//老办法， 先找hashi，也就是链表的位置。
//			int hashi = key % _tables.size();
//			node* cur = _tables[hashi];
//			node* prev = nullptr;
//			while (cur != nullptr) 
//			{
//				if (cur->_kv.first == key) 
//				{
//					if (prev == nullptr) 
//					{
//						_tables[hashi] = cur->_next;
//						delete cur;
//					}
//					else 
//					{
//						prev->_next = cur->_next;
//						delete prev;
//					}
//				}
//				cur = cur->_next;
//			}
//			return false;
//
//		}
//
//	private:
//		vector<node*> _tables;
//		size_t _n;
//	};
//
//
//
//}

//int re(int b) 
//{
//	return b;
//}
//
//#include<iostream>
//using namespace std;
//#include<string>
//
//#include"unorder_map.h"
//#include"unorder_set.h"
//
//int main() 
//{
//	string str[] = { "苹果", "梨", "香蕉", "桃子", "梨", "苹果", "梨", "香蕉", "桃子", "梨" , "苹果", "梨", "香蕉", "桃子", "梨" };
//	cws_hash_map::unorder_map<string, int> mp;
//
//	for (auto& e : str) 
//	{
//		mp[e]++;
//	}
//	for (auto& e : mp) 
//	{
//		cout << e.first << ":" << e.second << endl;;
//	}
//
//	return 0;
//}
//
//
//#include"bitset.h"
//
//int main()
//{
//	//size_t N = 4 * pow(10,5);
//	//cws_bit_set::bit_set<-1> bst;//传过去的相当于数据的个数
//
//	//srand(time(0));
//	//for (int i = 0; i < N; i++) 
//	//{
//	//	bst.set((rand() + i) % N);
//	//}
//
//	//for (int i = 0; i < N; i++) 
//	//{
//	//	if (bst.test(i)) 
//	//	{
//	//		cout << i << "---在" << endl;
//	//	}
//	//	else 
//	//	{
//	//		cout << i << "----不在" << endl;
//	//	}
//	//}
//
//
//	//bst.set(10);
//	//bst.set(13);
//	//bst.set(14);
//	//bst.set(15);
//
//	//cout << bst.test(10) << endl;
//	//cout << bst.test(13) << endl;
//	//cout << bst.test(14) << endl;
//	//cout << bst.test(15) << endl;
//
//	return 0;
//}
//
//
//#include <iostream>
//using namespace std;
//#include<vector>
//int main()
//{
//	int n = 0;
//	int m = 0;
//	int K = 0;
//	cin >> n;
//	cin >> m;
//	cin >> K;
//	cout << n << " " << m << " " << K << endl;
//	int count = 0;
//	vector<vector<int>> vv;
//	for (int i = 0; i < n; i++)
//	{
//		vector<int> v;
//		for (int j = 0; j < m; j++)
//		{
//			int a = 0;
//			cin >> a;
//			if (a == 1)
//			{
//				count++;
//			}
//			v.push_back(a);
//		}
//		vv.push_back(v);
//	}
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < m; j++)
//		{
//			cout << vv[i][j];
//		}
//		cout << endl;
//	}
//	//
//	for (int i = 0; i <= K; i++)
//	{
//		int num2 = K - i;
//		int num1 = i;
//		if (count == (num1 * 3 + num2 * 2))
//		{
//			cout << num1 << " " << num2;
//			return 0;
//		}
//	}
//
//	return 0;
//}
//
//#include"hashtable.h"
//using namespace cws_close;
//
//
//int main() 
//{
//
//	Hashtable<int, int> ht;
//	ht.insert(make_pair(1, 1));
//	ht.insert(make_pair(18, 1));
//	ht.insert(make_pair(2, 1));
//	ht.insert(make_pair(6, 1));
//	ht.insert(make_pair(5, 1));
//	ht.insert(make_pair(3, 3));
//	ht.insert(make_pair(13, 3));
//	ht.insert(make_pair(23, 3));
//	ht.insert(make_pair(33, 3));
//	ht.insert(make_pair(34, 3));
//	ht.insert(make_pair(35, 3));
//	ht.erase(34);
//	Hashtable<int, int> ht2;
//	ht2.insert(make_pair(35, 3));
//	ht2.insert(make_pair(55, 3));
//	ht2.insert(make_pair(366, 3));
//	ht2.insert(make_pair(5, 3));
//	ht2.insert(make_pair(315, 3));
//
//	ht.Swap(ht2);
//
//
//	return 0;
//}
//#include"hashtable.h"
//#include<iostream>
//using namespace std;
//
//
//int main() 
//{
//	HashBucket::Hashtable<int, int> ht;
//	ht.insert(3);
//	ht.insert(6);
//	ht.insert(4);
//	ht.insert(3);
//	ht.insert(2);
//
//	ht.insert(33);
//	ht.insert(244);
//	ht.insert(211);
//	ht.insert(234);
//	ht.insert(2456);
//	ht.insert(232);
//	ht.insert(12234);
//	ht.insert(22234);
//	ht.erase(211);
//	ht.clear();
//	ht.insert(2234);
//
//	return 0;
//}
//

//
//#include"unorder_map.h"
//
//int main() 
//{
//	cws_hash_map::unorder_map<int, int> mp;
//	vector<int> v(10, 1);
//
//	for (auto& e : v) 
//	{
//		mp[e]++;
//	}
//
//	for (auto& e : mp) 
//	{
//		cout << e.first <<":" << e.second << endl;
//	}
//
//	return 0;
//}


//
//#include"unorder_set.h"
//
//
//int main()
//{
//	cws_hash_set::unorder_set<int> st;
//	st.insert(14);
//	st.insert(112);
//	st.insert(121);
//	st.insert(12);
//	st.insert(13);
//	st.insert(9);
//
//	for (auto& e : st) 
//	{
//		cout << e << endl;
//	}
//
//	return 0;
//}
//#include"bitset.h"
//#include<time.h>
//using namespace cws_bitset;
//
//int main() 
//{
//	const int N = 10000;
//	BloomFilter<N, string> bmf;
//	srand(time(0));
//	for (int i = 0; i < N; i++) 
//	{
//		bmf.set(rand());//映射的个数其实就N个， 并且在映射的时候， bmf会自己进行处理。 
//	}
//
//张三 4 男 1
//李四 4 男 2
//王五 4 女 3
//白六 4 男 4
//成七 4 女 5
//
//	return 0;
//}


//
//
//#include"arr_stu.h"
//
//
//int main() 
//{
//	Array<student, 5> stu_arr;
//	for (int i = 0; i < 5; i++) 
//	{
//		stu_arr.push();
//	}
//
//	student* ptr = &stu_arr[0];
//	
//	cout << "第一个学生数据:" << ptr[0] << "第三个学生数据:" << ptr[2] << "第五个学生数据:" << ptr[4];
//
//	return 0;
//}
//

//5 23.5
//12 24.56
//100 21.5
//
//

//
//#include"calc_sum.h"
//
//int main() 
//{
//	store<staff> st(3);
//	st.Init();
//	
//	store<staff>::display(st);
//	double ret = store<staff>::average(st);
//	cout << "平均价格为:>" << ret << endl;
//
//	return 0;
//}

//程序填空
//程序改错（static， 菱形继承)
//读程序
//编程题

//#include"bitset.h"
//
//int main() 
//{
//	const int N = 10;
//	string str[] = { "苹果", "梨", "桃子", "排序", "字符串", "哈希", "红黑树", "优先级队列", "拓扑", "哈希桶" };
//	cws_bitset::bloomfilter<string, N> blm;
//
//	for (int i = 0; i < sizeof(str) / sizeof(str[1]); i++) 
//	{
//		blm.set(str[i]);
//
//	}
//
//	string str2 = "开散列";
//	cout << blm.test(str2) << endl;
//	string str3 = "苹果";
//	cout << blm.test(str3) << endl;
//
//	return 0;
//}

//对于海量数据， 如果有两个文件， 每一个文件有100亿个query， 但是我们只有1g的内存, 如何找到两个文件的交集；精确算法和近似算法是什么。 同时如何是bloomfilter支持
//删除元素的操作呢。

//位图的变形，对于一个文件有100亿个int	， 但是我们只有1g的内存， 设计算法找出不超过2次的整数。
//这里100亿个int， 10亿字节就是1g， 100亿字节就是10g， 然后int类型是char类型的4倍， 这里100亿个int就是40g， 只能保存在磁盘之中。 
//然后这里只能进行哈希切割。1g是10亿字节， 10亿字节就是80亿给比特位， 没一个比特位就能映射一个整数， 但是这里只需要40亿个比特位也就是512mb， 因为整数的最大数就是42亿九千万
//不过这里不能只使用512， 应该是使用1g。 因为这里要计数， 每一个整数的映射平均空间为2比特位
//所以这里就是将100亿分成三份， 每次处理42亿九千万
//
//#include"bitset.h"
//
//int main() 
//{
//
//	cws_bitset::bit_dou<5> bit;
//	bit.set(1);
//	bit.set(1);
//	bit.set(1);
//	bit.set(2);
//	bit.set(1);
//
//	cout << bit.test(1) << endl;
//	cout << bit.test(2) << endl;
//
//	return 0;
//}

//
//int main() 
//{
//	int a = 1;
//	int b = 2;
//
//	int&& ret = a + b;
//
//
//	return 0;
//}
//
//#include"string.h"
//
//int main() 
//{	
//	cws::string str1("hello");
//	cws::string str2("world");
//	 
//	cws::string str3 = str1.to_string(1);//这里调用了移动构造
//
//	return 0;
//}


//#include<iostream>
//using namespace std;
//#include<string.h>
//
//
//
//class Student 
//{
//public:
//	typedef size_t cls_num;
//	typedef size_t gra_num;
//
//	Student(const char* name = "", cls_num cls = 0, gra_num grade = 0)
//	{
//		_name = new char[strlen(name) + 1];
//		strcpy(_name, name);
//		_cls = cls;
//		_grade = grade;
//	}
//
//	~Student() 
//	{
//		delete _name;
//		_name = nullptr;
//		_cls = 0;
//		_grade = 0;
//	}
//
//	void display() 
//	{
//		cout << "姓名：" << _name << "班级:" << _cls << "年级:" << _grade;
//	}
//
//private:
//	char* _name;
//	cls_num _cls;
//	gra_num _grade;
//};



////编写一个学生类，学生信息包含姓名、 学号、 年龄、性别和成绩；（1） 输出每个学生
////的姓名、学号和成绩。（2） 统计并输出学生的总人数、 总成绩、 平均成绩、 最高成绩和最低
////成绩。
//
//
//
//
//
//#include"student.h"
//int main()
//{
//
//	cws::Student stu;
//	stu.push();
//	stu.push();
//	stu.Print();
//	stu.display();
//
//	return 0;
//}
//
//
//int main() 
//{
//
//	int* const p1 = new int;
//	//p1 = new int; //不可以， 因为p2是一个指针常量， 不能改变指向
//
//	int* p2 = p1;
//	p2 = new int;//这样就可以， 因为指针常量的值赋值给另一个不带常性的值， 这个不涉及权限的变化.
//
//
//	return 0;
//}


//
//int main()
//{
//	int a = 0;
//	int b = 1;
//	int c = a + b;
//
//	cout << c << endl;
//
//	peo p1("zhangsan", 18);//实例化
//
//	p1 = p1 + 2;//我们没有自己重载赋值符号。
//
//
//
//
//	return 0;
//}
//

//int main() 
//{
//	int a, b, c, d;
//	cin >> a >> b >> c >> d;
//	co



//
//struct index 
//{
//	int row = 1;
//	int col = 1;
//};
//
//int main() 
//{
//	vector<string> vs;
//	for (int i = 0; i < 10; i++) 
//	{
//		string str;
//		cin >> str;
//		vs.push_back(str);
//	}
//
//	index _index1;
//	index _index2;
//	int flag = 1;
//	int flag2 = 1;
//	for (int i = 0; i < 10; i++) 
//	{
//		for (int j = 0; j < 10; j++) 
//		{
//			if (vs[i][j] != '.') 
//			{
//				_index1.row = i;
//				_index1.col = j;
//				flag = 0;
//				break;
//			}
//		}
//		if (flag == 0) 
//		{
//			break;
//		}
//	}
//
//	for (int i = 9; i >= 0; i--)
//	{
//		for (int j = 9; j >= 0; j--)
//		{
//			if (vs[i][j] != '.')
//			{
//				_index2.row = i;
//				_index2.col = j;
//				flag2 = 0;
//				break;
//			}
//		}
//		if (flag2 == 0) 
//		{
//			break;
//		}
//	}
//
//	cout << _index1.row + 1 << " " << _index2.row + 1<< endl;
//	cout << _index1.col + 1 << " " << _index2.col  + 1<< endl;
//
//
//	return 0;
//}
//
//int main() 
//{
//	while (1.1) 
//	{
//		cout << " 1 " << endl;
//	}
//
//
//	return 0;
//}



//
//#include<iostream>
//using namespace std;
//#include<string>
//
//struct peo
//{
//	string _name;
//	int _age;
//
//	peo(string str = string(), int age = 0)
//		:_age(age)
//	{
//		_name = str;
//	}
//
//	peo operator+(const int x)
//	{
//		peo tmp = *this;
//		tmp._age += x;
//		return tmp;
//	}
//
//};
//
//int main() 
//{
//	int a = 1;
//	int b = 1;
//	int c = a + b;
//
//	cout << c << endl;
//
//	peo p1("zhangsan", 18);
//	p1 = p1 + 2;
//
//	return 0;
//}
//
//#include<iostream>
//using namespace std;
//#include<string>
//
//class student 
//{
//public:
//
//	student() 
//	{
//		student::_sum_grade += _grade;
//		student::num++;
//		student::_ave_grade = student::_sum_grade / student::num;
//	}
//
//	~student() 
//	{
//		student::_sum_grade -= _grade;
//		student::num--;
//		student::_ave_grade = student::_sum_grade / student::num;
//	}
//
//
//protected:
//	static int _sum_grade;
//	static int _ave_grade;
//	static size_t num;
//
//private:
//	string _name;
//	int _age;
//	string _num;
//	int _grade;
//};


//
//
//#include<iostream>
//using namespace std;
//#include<functional>
//#include<map>
//
//namespace cws
//{
//
//	template<class T>
//	class auto_ptr
//	{
//	public:
//		auto_ptr(const T* ptr)
//			:_ptr(ptr)//这里虽然没有给红线， 但是const T* 是无法给T* 赋值的。 所以这里是错误的。
//		{}
//
//		auto_ptr(const auto_ptr<T>& ptr)
//			:_ptr(ptr._ptr)
//		{}
//
//		auto_ptr()
//		{
//			delete _ptr;
//		}
//
//		T& operator*()
//		{
//			return *_ptr;
//		}
//
//		T* operator->()
//		{
//			return _ptr;
//		}
//
//	private:
//		T* _ptr;
//	};
//
//
//	template<class T>
//	class unique_ptr
//	{
//	public:
//		unique_ptr(T* ptr)
//			:_ptr(ptr)
//		{}
//
//		unique_ptr(const unique_ptr<T>& ptr) = delete;//将拷贝构造删掉， 令其无法拷贝
//
//		~unique_ptr() //默认生成的析构函数对于内置类型不做处理， 对于自定义类型会去调用它的析构函数。 所以这里要进行析构， 否则会发生内存泄漏
//		{
//			delete _ptr;
//		}
//
//		unique_ptr<T>& operator=(const unique_ptr<T>& ptr) = delete;//赋值拷贝也删掉
//
//		T& operator*()
//		{
//			return *_ptr;
//		}
//
//		T* operator->()
//		{
//			return _ptr;
//		}
//
//
//	private:
//		T* _ptr;
//
//	};
//
//	template<class T>
//	class share_ptr
//	{
//	public:
//		share_ptr(T* ptr)
//			:_ptr(ptr)
//			, _count(new int)
//		{
//			*_count = 1;
//		}
//
//		share_ptr(const share_ptr<T>& ptr)
//			:_ptr(ptr._ptr)
//			, _count(ptr._count)
//		{
//			(*_count) += 1;
//		}
//
//		template<class D>
//		share_ptr(T* ptr, D del)
//			:_ptr(ptr)
//			, _count(new int)
//			, _del(del)
//		{}
//
//		~share_ptr()
//		{
//			(*_count)--;
//			if (_count == 0)
//			{
//				delete _ptr;
//			}
//		}
//
//		share_ptr<T>& operator=(const share_ptr<T>& ptr)
//		{
//			if (_ptr == ptr._ptr)
//			{
//				return *this;
//			}
//			//
//			if (--(*_count) == 0)
//			{
//				delete _ptr;
//			}
//			_ptr = ptr._ptr;
//			_count = ptr._count;
//			(*_count)++;
//		}
//
//		T& operator*()
//		{
//			return *_ptr;
//		}
//
//		T* operator->()
//		{
//			return _ptr;
//		}
//
//	private:
//		T* _ptr;
//		int* _count;
//		function<void(T*)> _del =
//			[](T* ptr)
//			{
//				delete ptr;
//			};
//	};
//
//	class Copybon 
//	{
//	public:
//		Copybon(const Copybon& ban) = delete;
//
//	private:
//	};

	//只能在堆上创建对象

	//class HeapOnly 
	//{
	//public:

	//	//void Destory() 
	//	//{
	//	//	delete this;
	//	//}//可以这样将自己释放。 
	//	
	//	static void Destroy(HeapOnly* ptr) 
	//	{
	//		delete ptr;//也可以利用静态函数， 直接释放
	//	}


	//private:
	//	~HeapOnly()
	//	{
	//		cout << "~HeapOnly()" << endl;
	//	}

	//};
//
//	//第二种只能在堆上创建对象
//	class HeapOnly 
//	{
//	public:
//
//		static HeapOnly* CreatObj() 
//		{
//			return new HeapOnly;
//		}
//
//		//然后将拷贝构造禁掉
//		HeapOnly(const HeapOnly& hy) = delete;
//
//	private:
//		HeapOnly() 
//		{}//构造函数私有化
//	};
//
//
//	//只能在栈上创建对象
//	class StackOnly 
//	{
//	public:
//		static StackOnly CreatObj() 
//		{
//			StackOnly obj;
//			return obj;//注意， 这里不能返回指针， 因为obj是栈上开辟的空间。 函数声明周期结束时这个局部对象就被销毁了。 
//		}
//
//		//如过不想让new的拷贝构造能用。 就要禁掉拷贝构造。 但是禁掉拷贝构造之后， creatobj就不能用了。所以应该将new干掉
//		void* operator new(size_t size) = delete;//这里要加一个数量
//
//	private:
//		//禁掉构造函数， 直接让它不能初始化
//		StackOnly()
//		{}
//	}; 
//
//	//单例模式
//
//	//饿汉模式
//	class A
//	{
//	public:
//		static A* GetInstance() 
//		{
//			return &_inst;
//		}
//
//		void insert(const string& key, const string& value) 
//		{
//			_dict[key] = value;
//		}
//
//		void print() 
//		{
//			for (auto& e : _dict) 
//			{
//				cout << e.first << ":" << e.second << endl;
//			}
//		}
//
//	private:
//		A()
//		{}
//
//
//		map<string, string> _dict;
//
//		int _n = 0;
//
//		static A _inst;
// 	};
//
//	//懒汉模式
//
//	class B 
//	{
//	public:
//		static B* Getinstance() 
//		{
//			if (_inst == nullptr) 
//			{
//				_inst = new B;
//			}
//			return _inst;
//		}
//
//
//
//
//	private:
//		static B* _inst;
//
//	};
//
//
//}
//
//cws::A cws::A::_inst = A();
//cws::B* cws::B::_inst = nullptr;
//
//int main()
//{
//
//	cws::A::GetInstance()->insert("left", "左边");
//	cws::A::GetInstance()->print();
//
//	return 0;
//}
//
//



//
//void insert(size_t pos) 
//{
//	int end = 10;
//	while (end >= pos) 
//	{
//		cout << end << endl;//end大于等于0；
//		end--;
//	}
//}
////
//class A 
//{
//public:
//	int _a;
//
//};
//
//class B : public A
//{
//public:
//	int _b;
//};
//
//void rever(A* ptr) //如果本身指向父类， 那么就转换失败了。 如果本身是子类的， 那么转换就成功了。
//{
//	B* p = (B*)ptr;
//	p->_a++;
//	p->_b++;
//}




//
//template<class T>
//class DelArray 
//{
//public:
//
//	void operator()(T* ptr) 
//	{
//		delete[] ptr;
//	}
//
//};
//

//int main()
//{
//	//cws::share_ptr<int> p1 = new int(1);
//	//*p1 = 2;
//	//cout << *p1 << endl;
//
//
//	//cws::share_ptr<int> p2 = p1;
//	//*p2 = 3;
//	//cout << *p2 << endl;
//
//	//std::shared_ptr<string> p1(new string[10], DelArray<string>());//定制删除器;
//
//	//std::shared_ptr<FILE> fp(fopen("text", "r"), 
//	//	[](FILE* ptr)
//	//	{
//	//		fclose(ptr);
//	//	}
//	//);//这里使用了定制删除器解决问题。
//
//	cws::HeapOnly* heap = new cws::HeapOnly;//这里因为析构函数被干掉了， 所以heap不能直接在栈上创建。 必须在堆上创建。 
//
//
//	return 0;
//}
//


//
//class A 
//{
//public:
//	A() 
//	{
//		a = 0;
//		b = 0;
//	}
//	A(int i) 
//	{
//		a = i;
//		b = 0;
//	}
//	A(int i, int j) 
//	{
//		a = i;
//		b = j;
//	}
//	void display() 
//	{
//		cout << "a=" << a << " b=" << b;
//	}
//
//private:
//	int a;
//	int b;
//};
//
//class B : public A
//{
//public:
//	B()
//	{
//		c = 0;
//	}
//	B(int i)
//		: A(i)
//	{
//		c = 0;
//	}
//	B(int i, int j)
//		:A(i, j)
//	{
//		c = 0;
//	}
//	B(int i, int j, int k)
//		:A(i, j)
//	{
//		c = k;
//	}
//	void display1()
//	{
//		display();
//		cout << " c=" << c << endl;
//	}
//
//private:
//	int c;
//};
//


//#include<iostream>
//using namespace std;
//#include<string>
//
//class Teacher 
//{
//public:
//
//	Teacher(string name, int age, string sex, string adress, string tele, string tit) 
//		:_name(name)
//		,_age(age)
//		,_grander(sex)
//		,_adress(adress)
//		,_tele(tele)
//		,_title(tit)
//	{}
//	void display() 
//	{	
//		cout << "姓名:" << _name << "	年龄:" << _age << "	性别:" << _grander << "	地址:" << _adress << "	电话:" << _tele << "	职称:" << _title << endl;
//	}
//
//protected:
//	string _name;    //名称
//	int _age;        //年龄
//	string _grander; //性别
//	string _adress;  //地址
//	string _tele;    //电话
//	string _title;   //职称
//};
//
//class Cadre
//{
//public:
//	Cadre(string name, int age, string sex, string adress, string tele, string post)
//		:_name(name)
//		, _age(age)
//		, _grander(sex)
//		, _adress(adress)
//		, _tele(tele)
//		, _post(post)
//	{}
//
//protected:
//	string _name;    //名称
//	int _age;        //年龄
//	string _grander; //性别
//	string _adress;  //地址
//	string _tele;    //电话
//	string _post;   //职务
//};
//
//
//class Teacher_Cadre : public Teacher, public Cadre
//{
//public:
//
//	Teacher_Cadre(string name, int age, string sex, string adress, string tele, string tit, string post, int wages)
//		:Teacher(name, age, sex, adress, tele, tit)
//		,Cadre(name, age, sex, adress, tele, post)
//	{
//		_wages = wages;
//	}
//
//	void show() 
//	{
//		Teacher::display();
//		cout << "职务:" << Cadre::_post << "	  工资:" << _wages;
//	}
//	
//private:
//	int _wages;
//	
//};
//
//int main() 
//{
//
//	Teacher_Cadre tc = { "张三", 30, "男", "河南", "1111111", "数学老师", "教授课程", 5000 };
//	tc.show();
//
//	return 0;
//}
////
////void test() 
////{
////	for (int i = 0; i < 10; i++) 
////	{
////		printf("%d\n", i);
////	}
////}
////
////
////void test1() 
////{
////	int i = 0;
////	int a = 0;
////	int b = 0;
////	scanf("%d %d %d", &a, &b, &i);
////
////	printf("%d %d %d", a, b, i);
////}
////
////
////void func1() 
////{
////	int N;
////
////	scanf("%d", &N);
////
////	for (int i = 0; i < N; i++)
////	{
////		printf("%d", i);
////	}
////
////	for (int i = 0; i < N; i++) 
////	{
////		for (int j = 0; j < N; j++) 
////		{
////			printf("%d", j);
////		}
////		printf("\n");
////	}
////	
//}
//
//int main() 
//{
//	int a = 0;
//	int b = 0;
//	scanf("%d %d", &a, &b);
//
//	while (a % b != 0) 
//	{
//		int tmp = a % b;
//		a = b;
//		b = tmp;
//	}
//
//	printf("%d", b);
//
//
//}




//
//
//#include<iostream>
//using namespace std;
//#include<vector>
//#include<string>
//#include<unordered_map>

//
//int main() 
//{
//
//	vector<string> vs;
//
//
//	int N;
//	cin >> N;
//
//	int left = 0;
//	int right = 0;
//	int count = 0;
//
//	for (int i = 0; i < N; i++) 
//	{
//		string str;
//		cin >> str;
//		vs.push_back(str);
//	}
//	unordered_map<string, int> hash;
//
//	cout << endl << endl << endl;
//	while (right < N) 
//	{
//		hash[vs[right]]++;
//		while (right > 0 && vs[right] != vs[left]) 
//		{
//			left++;
//		}
//		if (hash[vs[right]] == 1)
//		{
//			cout << vs[right] << endl;
//		}
//		else 
//		{
//			cout << vs[right] << "(" << (hash[vs[right]] - 1) << ")" << endl;
//		}
//		right++;
//	}
//	return 0;
//}

#include<time.h>

//void func2()
//{
//	int N;
//	scanf("%d", &N);
//
//
//	int begin1 = clock();//进入循环前，记一下时间
//
//	for (int i = 0; i < N; i++)
//	{
//		int x = 1;
//	}
//
//	int end1 = clock();//出循环后， 记一下时间
//
//
//	int begin2 = clock();//进入第二个循环前， 记一下时间
//
//	for (int i = 0; i < N; i++)
//	{
//		for (int j = 0; j < N; j++)
//		{
//			int y = 1;
//		}
//	}
//
//	int end2 = clock();//出第二个循环前， 记一下时间。 
//
//	
//	int time1 = end1 - begin1;//time1就是第一个循环所消耗的时间
//	int time2 = end2 - begin2;//time2就是第二个循环所消耗的时间
//
//
//	//对这两次的时间进行打印:
//	cout << "N时间为: " << time1 << endl;
//	cout << "N^2时间为: " << time2 << endl;
//
//}
//
//void test1(int n) 
//{
//	int x = 0;
//	for (int i = 0; i < n; i++) 
//	{
//		x++;
//	}
//
//	int k = 10;
//	for (int i = 0; i < k; i++) 
//	{
//		x++;
//	}
//}
//
//
//void test2(int n, int k)
//{
//	int x = 0;
//	for (int i = 0; i < n; i++)
//	{
//		x++;
//	}
//
//	for (int i = 0; i < k; i++)
//	{
//		x++;
//	}
//}
//
//void test3(int n)
//{
//	int x = 0;
//	for (int i = 0; i < 50; i++) 
//	{
//		x++;
//	}
//}
//
//void BubbleSort(int* a, int n)
//{
//	for (size_t end = n; end > 0; --end)
//	{
//		int exchange = 0;
//		for (size_t i = 1; i < end; ++i)
//		{
//			if (a[i - 1] > a[i])
//			{
//				swap(a[i - 1], a[i]);
//				exchange = 1;
//			}
//		}
//		if (exchange == 0)
//			break;
//	}
//}
//int BinarySearch(int* a, int n, int x)
//{
//	int begin = 0;
//	int end = n - 1;
//	// [begin, end]：begin和end是左闭右闭区间，因此有=号
//	while (begin <= end)
//	{
//		int mid = begin + ((end - begin) >> 1);
//		if (a[mid] < x)
//			begin = mid + 1;
//		else if (a[mid] > x)
//			end = mid - 1;
//		else
//			return mid;
//	}
//	return -1;
//}
//
//long long* Fibonacci(size_t n)
//{
//	if (n == 0)
//		return NULL;
//	long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
//	fibArray[0] = 0;
//	fibArray[1] = 1;
//	for (int i = 2; i <= n; ++i)
//	{
//		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
//	}
//	return fibArray;
//}
//
//int main()
//{
//
//	return 0;
//}

//
////第一题
//class Person 
//{
//public:
//	Person(int num = 0, string name = string()) 
//		:_num(num)
//		,_name(name)
//	{}
//	void display() 
//	{
//		cout << "编号:" << _num << "		" << "姓名:" << _name << "	";
//	}
//
//protected:
//	int _num;
//	string _name;
//};
//
//
////学生类
//class Student : public Person
//{
//public:
//	//学生类默认构造
//	Student(int num = 0, string name = string(), string cls = string(), int grade = 0)
//		:Person(num, name)
//		,_class(cls)
//		,_grade(grade)
//	{}
//	//展示
//	void display()
//	{
//		Person::display();
//		cout << "职称:" << _class << "	 " << "部门:" << _grade << endl;
//	}
//
//
//private:
//	string _class; //班级
//	int _grade;    //成绩
//};
//
////教师类
//class Teacher : public Person 
//{
//public:
//	//教师类默认构造
//	Teacher(int num = 0, string name = string(), string title = string(), string sector = string()) 
//		:Person(num, name)
//		,_title(title)
//		,_sector(sector)
//	{}
//	//展示
//	void display() 
//	{
//		Person::display();
//		cout << "职称:" << _title << "	 " << "部门:" << _sector << endl;
//	}
//
//private:
//	string _title;   //职称
//	string _sector;  //部门
//};
//
//
//int main() 
//{
//	//创建教师对象
//	Teacher t1(1, "张三", "数学老师", "数学部");
//	Teacher t2(2, "李四", "语文老师", "语文部");
//	Teacher t3(2, "王五", "英语老师", "英语部");
//	//打印教师对象
//	t1.display();
//	t2.display();
//	t3.display();
//
//	//创建学生对象
//	Student s1(1, "小明", "计科233", 10);
//	Student s2(2, "小王", "计科234", 12);
//	Student s3(3, "小红", "计科235", 13);
//	//打印学生对象
//	s1.display();
//	s2.display();
//	s3.display();
//
//
//
//	return 0;
//}

//
//
//#include<iostream>
//using namespace std;
//#include"RBTree.h"
//#include"map.h"
//
//
//int main() 
//{
//	cws_map::map<int, int> mp;
//	mp.insert(make_pair(1, 2));
//	mp.insert(make_pair(5, 2));
//	mp.insert(make_pair(8, 2));
//	mp.insert(make_pair(2, 2));
//	mp.insert(make_pair(1, 2));
//	mp.insert(make_pair(3, 2));
//	mp.insert(make_pair(4, 2));
//
//	auto it = mp.begin();
//	while (it != mp.end()) 
//	{
//		cout << (*it).first << " ";
//		++it;
//	}
//	cout << endl;
//	for (auto& e : mp) 
//	{
//		cout << e.first << " ";
//	}
//	cout << endl;
//
//	return 0;
//}

//
//
//
//class Person
//{
//public:
//	Person(int time = 0, int sale = 0)
//		:_time(time)
//		, _sales(sale)
//	{}
//protected:
//	int _time; //花费时间
//	int _sales; //销售金额
//};
//
//
////公司经理
//class com_manger :public Person
//{
//public:
//	com_manger(int time = 0, int sales = 0)
//		:Person(time, sales)
//	{}
//	//计算工资
//	void calc_wages()
//	{
//		cout << "公司经理的工资为:" << _wages << endl;
//	}
//protected:
//	int _wages = 18000;
//};
//
////兼职人员
//class part_emp :public Person
//{
//public:
//	part_emp(int time = 0, int sales = 0)
//		:Person(time, sales)
//	{}
//
//	//计算工资
//	void calc_wages()
//	{
//		cout << "兼职人员的工资为:" << _time_wages * _time << endl;;
//	}
//protected:
//	int _time_wages = 200;
//};
//
////销售经理
//class  sale_manger : public Person
//{
//public:
//	sale_manger(int time = 0, int sales = 0)
//		:Person(time, sales)
//	{}
//	//计算工资
//	void calc_wages()
//	{
//		cout << "销售经理的总工资为:" << _stable_wages + _com * _sales << endl;
//	}
//protected:
//	int _stable_wages = 6000;
//	double _com = 0.01;
//};
//
//
////销售员
//class sale_emp : public Person
//{
//public:
//	sale_emp(int time = 0, int sales = 0)
//		:Person(time, sales)
//	{}
//
//	//计算工资
//	void calc_wages()
//	{
//		cout << "销售员的总工资:" << _com * _sales << endl;
//	}
//protected:
//	double _com = 0.08;
//};

//
//#include<time.h>
//#include<stdio.h>
//
//void func2()
//{
//	int N;
//	scanf("%d", &N);
//
//
//	int begin1 = clock();//进入循环前，记一下时间
//
//	for (int i = 0; i < N; i++)
//	{
//		int x = 1;
//	}
//
//	int end1 = clock();//出循环后， 记一下时间
//
//
//	int begin2 = clock();//进入第二个循环前， 记一下时间
//
//	for (int i = 0; i < N; i++)
//	{
//		for (int j = 0; j < N; j++)
//		{
//			int y = 1;
//		}
//	}
//
//	int end2 = clock();//出第二个循环前， 记一下时间。 
//
//
//	int time1 = end1 - begin1;//time1就是第一个循环所消耗的时间
//	int time2 = end2 - begin2;//time2就是第二个循环所消耗的时间
//
//
//	//对这两次的时间进行打印:
//	printf("N时间为:%d\n", end1 - begin1);
//	printf("N^2时间为:%d\n", end2 - begin2);
//
//}
//
//int main()
//{
//	func2();
//
//	return 0;
//}

//
//#include<iostream>
//using namespace std;
//
//class Real
//{
//public:
//	//构造函数
//	Real(double real = double())
//		:_real(real)
//	{}
//
//	//打印函数
//	void display()
//	{
//		cout << _real << endl;
//	}
//
//	////////////////////////////operator
//	Real operator+(Real x) 
//	{
//		return Real(_real + x._real);
//	}
//
//	Real operator-(Real x) 
//	{
//		return Real(_real - x._real);
//	}
//
//	Real operator*(Real x) 
//	{
//		return Real(_real * x._real);
//	}
//
//	Real operator/(Real x) 
//	{
//		return Real(_real / x._real);
//	}
//
//protected:
//	double _real;
//};
//
//class Complex : public Real 
//{
//public:
//	//友元声明
//	friend ostream& operator<<(ostream& out, const Complex& x);
//
//
//	//构造函数
//	Complex(double real = double(), double image = double()) 
//		:Real(real)
//		,_image(image)
//	{}
//
//	Complex operator+(Complex x) 
//	{
//		return Complex(_real + x._real, _image + x._image);
//	}
//
//
//	Complex operator-(Complex x)
//	{
//		return Complex(_real - x._real, _image - x._image);
//	}
//
//
//	Complex operator*(Complex x)
//	{
//		return Complex(_real * x._real - _image * x._image, _image * x._real + _real * x._image);
//	}
//
//	Complex operator/(Complex x)
//	{
//		return Complex((_real * x._real + _image * x._image) / (x._real * x._real + x._image * x._image), (_image * x._real - _real * x._image) / (x._real * x._real + x._image * x._image));
//	}
//
//
//protected:
//	double _image;
//};
//
//ostream& operator<<(ostream& out, const Complex& x) 
//{
//	out <<"结果为：" <<  x._real << "+" << x._image << "i";
//	return out;
//}
//
//
//void calc() 
//{
//	int input;
//	double a, b, c, d;
//	do 
//	{
//
//		cout << "请输入你要操作的第一个复数:>(提示：输入两个数， 分别表示第一个复数的实数部分和虚数部分)";
//		cin >> a >> b;
//
//		cout << "请输入你要操作的第二个复数:>(提示：输入两个数， 分别表示第二个复数的实数部分和虚数部分)";
//		cin >> c >> d;
//		Complex k1(a, b);
//		Complex k2(c, d);
//
//
//		cout << "请输入你要进行的计算:" << endl;
//		cout << "**************************************" << endl;
//		cout << "****             1. Add           ****" << endl;
//		cout << "****             2. Sub           ****" << endl;
//		cout << "****             3. Mul           ****" << endl;
//		cout << "****             4. dvi           ****" << endl;
//		cout << "****             5.exit           ****" << endl;
//		cout << "**************************************" << endl;
//
//
//		cin >> input;
//
//		switch (input) 
//		{
//		case 1 : 
//			cout << k1 + k2 << endl;
//			break;
//		case 2 :
//			cout << k1 - k2 << endl;
//			break;
//		case 3:
//			cout << k1 * k2 << endl;
//			break;
//		case 4 :
//			cout << k1 / k2 << endl;
//			break;
//		}
//
//
//
//	} while (input);
//}
//
//int main() 
//{
//	calc();
//	
//	return 0;
//}


#include<iostream>
using namespace std;
#include<string>
#include<vector>
#include<stack>
#include<map>
#include<algorithm>
//struct index 
//{
//	index(int n1, int n2) 
//		:x(n1)
//		,y(n2)
//	{}
//	int x = 0;
//	int y = 0;
//};
//
//
//void my_search(vector<vector<char>>& vv, int h, stack<index>& st, size_t& _max, int x, int y) 
//{
//	if (x < 0 || x > 4 || y < 0 || y > vv.size() - 1) 
//	{
//		return;
//	}
//	if (vv[x][y] == '1') 
//	{
//		return;
//	}
//
//	int flag = 1;
//	if (vv[x][y] == '*') 
//	{
//		st.push({ x, y });
//		h--;
//		flag = 0;
//	}
//	else if (vv[x][y] == '#') 
//	{
//		h--;
//	}
//	vv[x][y] = '1';
//
//	//
//	if (h == 0) 
//	{
//		_max = max(st.size(), _max);
//		if (flag == 0) 
//		{
//			st.pop();
//			vv[x][y] = '*';
//		}
//		else 
//		{
//			vv[x][y] = '#';
//		}
//		return;
//	}
//
//	my_search(vv, h, st, _max, x - 1, y);
//	my_search(vv, h, st, _max, x, y - 1);
//	my_search(vv, h, st, _max, x, y + 1);
//	my_search(vv, h, st, _max, x + 1, y);
//
//	if (x == 2) 
//	{
//		;
//	}
//	else 
//	{
//		if (flag == 0) 
//		{
//			vv[x][y] = '*';
//		}
//		else 
//		{
//			vv[x][y] = '#';
//		}
//	}
//
//}
//
//int main() 
//{
//	int n = 0;
//	int h = 0;
//	cin >> n >> h;
//	vector<vector<char>> vv(5, vector<char>(n));
//
//	for (int i = 0; i < 5; i++) 
//	{
//		for (int j = 0; j < n; j++) 
//		{
//			cin >> vv[i][j];
//		}
//	}
//	stack<index> st;
//	size_t _max = 0;
//	my_search(vv, h, st, _max, 0, 0);
//	cout << _max << endl;
//	return 0;
//}
//
//
//int main() 
//{
//	int a = -1;
//	int b = a << 1;
//	cout << b << endl;
//	cout << (b << 1) << endl;
//	return 0;
//}


//int main()
//{
//	calc();
//
//	return 0;
//}
//
//
//int main() 
//{
//	int suma = 0;
//	int sumb = 0;
//	for (int i = 0; i < 9; i++) 
//	{
//		int a = 0;
//		cin >> a;
//		suma += a;
//	}
//	for (int j = 0; j < 8; j++) 
//	{
//		int b = 0;
//		cin >> b;
//		sumb += b;
//	}
//
//	cout << suma - sumb + 1 << endl;
//	return 0;
//}

//
//
//int main() 
//{
//	int n = 0;
//	cin >> n;
//	vector<int> v(n);
//	for (int i = 0; i < n; i++) 
//	{
//		cin >> v[i];
//	}
//
//	int sum = 0;
//	for (int i = 0; i < n; i++) 
//	{
//		for (int j = i + 1; j < n; j++) 
//		{
//			sum += max(v[j] - v[i], 0);
//		}
//	}
//
//	cout << sum;
//	return 0;
//}
//
//
//#include <iostream>
//using namespace std;
//#include<string>
//void solveSudoku(vector<vector<char>>& board)
//{
//    b_col.resize(9, vector<bool>(10, false));
//    b_row.resize(9, vector<bool>(10, false));
//    block.resize(3, vector<vector<bool>>(3, vector<bool>(10, false)));
//    //先计数
//    for (int i = 0; i < 9; i++)
//    {
//        for (int j = 0; j < 9; j++)
//        {
//            if (board[i][j] != '.')
//            {
//                count++;
//                int in = board[i][j] - '0';
//                b_col[j][in] = true;
//                b_row[i][in] = true;
//                block[i / 3][j / 3][in] = true;
//            }
//        }
//    }
//    dfs(board, 0, 0);
//}
//vector<vector<bool>> b_row;
//vector<vector<bool>> b_col;
//vector<vector<vector<bool>>> block;
//int count = 0;
//bool game = false;
//
////我的dfs的使命就是， 对于当前位置填上一个数字。 形成9路分支。 然后向上， 向下， 向左， 向右进行搜索。 
////但是会有重复的情况。 这个时候就用到了剪枝。 如果该位置有数字， 我们不需要再形成九路分支， 直接在上下左右探索即可.
////第一种剪枝是row 和 col的坐标问题. 
////第二种剪枝就是，我们形成9路分支的时侯， 某一分支不匹配。 那么就不是正确的。 该条分支直接干掉。 
////然后就是结束条件。 结束条件我们可以利用一个count进行技术。 只要填好一个格子（也就是进入一个分支我们就加1）回溯的时候我们再将count变回来进入下一个分支即可
//void dfs(vector<vector<char>>& nums, int row, int col)
//{//函数头需要传送行坐标和列坐标。 为了定位某一个位置
//    if (row < 0 || col < 0 || row >= 9 || col >= 9) return;
//    if (count == 81)
//    {
//        game = true;
//        return;
//    }              //如何才能防止答案不会被覆盖。那就要在路上设置剪枝操作。 如果true了， 就只返回就行， 不再搜索
//    if (nums[row][col] != '.')  //dfs的作用是什么。 搜索支路。
//    {
//        dfs(nums, row + 1, col);
//        dfs(nums, row - 1, col);
//        dfs(nums, row, col - 1);
//        dfs(nums, row, col + 1);
//        return;
//    }
//
//    //九路分支
//    for (int i = 1; i <= 9; i++)
//    {
//        //剪枝
//        if (b_row[row][i] || b_col[col][i] || block[row / 3][col / 3][i])  continue;
//        //搜索形成支路
//        if (game) return;
//        nums[row][col] = i + '0';
//        b_row[row][i] = true;
//        b_col[col][i] = true;
//        block[row / 3][col / 3][i] = true;
//        count++;
//
//        //又一个问题， 这里需不需要恢复现场？ 那就需要知道dfs的作用是什么。 
//        //其实dfs的作用就是对当前节点进行支路搜索。 填上1， 搜索上下左右。填上2搜索上下左右。
//        dfs(nums, row + 1, col);
//        dfs(nums, row - 1, col);
//        dfs(nums, row, col - 1);
//        dfs(nums, row, col + 1);
//
//
//        //该条支路上下左右搜索完成后。 就复原现场
//        count--;
//        b_row[row][i] = false;
//        b_col[col][i] = false;
//        block[row / 3][col / 3][i] = false;
//        nums[row][col] = '.';
//    }
//
//}


//
//int main() 
//{
//	int n, x, y, z;
//	cin >> n >> x >> y >> z;
//	
//	int k = max(x, y);
//	if (n < max(k, z)) cout << "No" << endl;
//	else 
//	{
//		int _min = min(x, y);
//		int _max = max(x, y);
//		if (z >= _min && z <= _max) 
//		{
//			cout << "Yes" << endl;
//		}
//		else 
//		{
//			cout << "No" << endl;
//		}
//	}
//
//	return 0;
//}

//
//int main() 
//{
//	string str1;
//	string str2;
//	cin >> str1 >> str2;
//
//	int index1 = 0;
//	int index2 = 0;
//
//	while (index2 < str2.size()) 
//	{
//		if (str1[index1] == str2[index2]) 
//		{
//			cout << index2 + 1 << " ";
//			index1++;
//		}
//		index2++;
//	}
//
//	return 0;
//}
//#include<iostream>
//using namespace std;
//#include<string>
//#include<vector>
//int main() 
//{
//	int n = 0;
//	cin >> n;
//	vector<vector<long long>> man(n, vector<long long>(2));
//	long long sum = 0;
//	for (int i = 0; i < n; i++) 
//	{
//		cin >> man[i][0] >> man[i][1];
//		sum += man[i][0];
//	}
//	long long _max = 0;
//	for (int i = 0; i < n; i++) 
//	{
//		_max = max(_max, sum - man[i][0] + man[i][1]);
//	}
//
//	cout << _max << endl;
//	return 0;
//}
//
//
//

//int main() 
//{
//	int n = 0;
//	int k = 0;
//	cin >> n >> k;
//	vector<int> time(n + 1, 0);
//	for (int i = 1; i < time.size(); i++) 
//	{
//		cin >> time[i];
//	}
//
//	int sum = 0;
//	vector<long long> dp(n + 1, 0);
//	for (int i = 1; i <= k; i++) 
//	{
//		dp[k] += time[i];
//	}
//	for (int i = k + 1; i < time.size(); i++) 
//	{
//		dp[i] = dp[i - 1] + time[i] - time[i - k];
//	}
//	double kb = 0;
//	for (int i = k; i < time.size(); i++) 
//	{
//		kb = dp[i];
//		double output = kb / k;
//		if (output > (double)1024) 
//		{
//			printf("%f MiBps\n", output / 1024);
//		}
//		else 
//		{
//			printf("%f KiBps\n", output);
//		}
//	}
//
//
//
//	return 0;
//}

//
//int main() 
//{
//	//int a[10] = { 0, 1, 2, 3, 4, 4, 5, 6, 7, 8 };
//	//HeapSort(a, 10);
//	//for (int i = 0; i < 10; i++) 
//	//{
//	//	cout << a[i] << " ";
//	//}
//
//
//
//	return 0;
//}

//
//
//namespace cws 
//{
//	template<class K, class V>
//	class AVLTreeNode 
//	{
//		AVLTreeNode<K, V>* _left;
//		AVLTreeNode<K, V>* _right;
//		AVLTreeNode<K, V>* _parent;//三叉链
//		pair<K, V> _kv;
//		int _bf; // balance factor 平衡因子
//
//		AVLTreeNode(const pair<K, V> kv = pair<K, V>()) //节点的构造函数
//			:_left(nullptr)
//			,_right(nullptr)
//			,_parent(nullptr)
//			,_kv(kv)
//			,_bf(0)
//		{}
//	};
//
//	template<class K, class V>
//	class AVLTree 
//	{
//		typedef AVLTreeNode<K, V> node;
//	public:
//		bool Insert(const pair<K, V> kv) //pair就是值
//		{
//			if (_root == nullptr) 
//			{
//				_root = new node(kv);
//				return true;
//			}
//			else 
//			{
//				node* parent = nullptr;
//				node* cur = _root;
//				while (cur != nullptr) 
//				{
//					parent = cur;
//					if (kv->first > cur->_kv->first) 
//					{
//						parent = cur;
//						cur = cur->_right;
//					}
//					else if (kv->first < cur ->_kv->first) 
//					{
//						parent = cur;
//						cur = cur->_left;
//					}
//					else 
//					{
//						return false;
//					}
//				}
//				//走到这里， 说明cur已经走到了空的位置。 可以进行插入了。
//				cur = new node(kv);
//				if (kv.first > parent->_kv.first)//parent链接cur节点
//				{
//					parent->_right = cur;
//				}
//				else 
//				{
//					parent->_left = cur;
//				}
//				cur->_parent = parent;//第三链指向根节点.
//				
//				//判断平衡因子
//				while (parent) 
//				{
//					if (cur == parent->_right) 
//					{
//						parent->_bf++;
//					}
//					else 
//					{
//						parent->_bf--;
//					}
//					//
//					if(parent->_bf == 1 || parent->_bf == -1) 
//					{
//						parent = parent->_parent;
//						cur = cur->_parent;
//
//					}
//					else if (parent->_bf == 0) 
//					{
//						break;
//
//					}
//					else if (parent->_bf == -2 || parent->_bf == 2) 
//					{
//						//旋转节点
//					}
//					else 
//					{
//						assert(flase);
//					}
//
//				}
//
//
//				
//
//				//
//				return true;
//			}
//
//
//		}
//
//
//
//	private:
//
//		node* _root;
//
//
//	};
//
//}
//

// 
//class Person 
//{
//public:
//	//构造函数
//	Person(string name, string sex) 
//		:_name(name)
//		,_sex(sex)
//	{
//		cout << "Person()" << endl;
//	}
//
//	string _name = "张三";        //姓名
//	string _sex = "男";         //性别
//	static int sum;
//};
//int Person::sum = 100;
//
//class Student : public Person 
//{
//public:
//	Student(string name = "张三", string sex = "男", int num = 111)
//		:_num(num)
//		,Person(name, sex)
//	{
//		cout << "Student()" << endl;
//	}
//
//	int _num = 111;            //学号
//};
//
//
//int main() 
//{
//	Student stu("张三", "男", 44);
//	Person st = stu;
//	cout << Person::sum << endl;
//}


#include<iostream>
using namespace std;
#include<vector>
#include<string>



//class A 
//{
//public:
//	A() 
//	{
//		cout << "A()" << endl;
//	}
//
//	int _a = 0x11;   //定义一个变量_a
//};
//
////B类继承A
//class B : virtual public A   //B继承A后， 有一份_a
//{
//public:
//	B() 
//	{
//		cout << "B()" << endl;
//	}
//	int _b = 0x22;
//};
//
////C类继承B
//class C : virtual public A   //C继承A后， 有一份_a
//{
//public:
//	C() 
//	{
//		cout << "C()" << endl;
//	}
//	int _c = 0x33;
//};
//
//class D : public B, public C      //D继承B， C类， 这样D中就有了两份_a。
//{
//public:
//	D() 
//	{
//		cout << "D()" << endl;
//	}
//	int _d = 0x44;
//};
//
//
//int main() 
//{
//	D d2;
//
//	//切片，b中有_b, _a。 所以要找到d2中的B类数据域和A类数据域。 
//	B b = d2;
//	//同上。
//	C c = d2;
//
//}
//
//#include<stdio.h>
//int main()
//{
//	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
//	int i = 0;
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	int key = 0;
//	
//	printf("请输入想要查找的数:");
//	scanf("%d", &key);
//
//	while (i < sz)
//		if (arr[i] == key)
//	{
//		{
//			printf("\n找到了，元素下标是%d\n", i);
//			break;
//		}
//		i++;
//	}
//
//	if (i > sz - 1)
//	{
//		printf("\n元素找不到\n");
//	}
//	return 0;
//}
//
//
//
//
////向上调整
//void  Adjustup(int* _data, int i)
//{
//	int child = i;
//	int parent = (child - 1) / 2;
//	//建小堆
//	while (child > 0)
//	{
//		if (_data[child] < _data[parent]) swap(_data[child], _data[parent]);
//		else break;
//
//		child = parent;
//		parent = (child - 1) / 2;
//	}
//}
//
////向下调整
//void AdjustDown(int* _data, int end, int parent)  //第一个参数是要调整的数组， 第二个参数是要调整到的最后一个元素， 然后第三个参数是起始调整的位置, 当向下调整建堆的时候就需要用到第三个参数， 但是进行排序的时候是不需要的
////并且建小堆是排的降序
//{
//	int child = parent * 2 + 1;
//	while (child <= end)
//	{
//		if (child + 1 <= end && _data[child + 1] < _data[child])
//		{
//			child++;
//		}
//
//		if (_data[child] < _data[parent]) swap(_data[child], _data[parent]);
//		else break;
//		parent = child;
//		child = parent * 2 + 1;
//	}
//}
//
//void HeapSort(int* _data, int sz)
//{
//
//	for (int i = ((sz - 1) - 1) / 2; i >= 0; i--)
//	{
//		AdjustDown(_data, sz - 1, i); //向下调整建小堆， 从最后一个有子节点的节点开始进行建堆。 
//	}
//
//	//排序， 过程是先将第一个数据和最后一个数据交换一下位置，然后减减数组大小,然后从0索引开始向下建堆。
//	for (int i = sz - 1; i > 0; i--)
//	{
//		swap(_data[0], _data[i]);
//		AdjustDown(_data, i - 1, 0);
//	}
//}
//
//int main() 
//{
//	int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
//
//	HeapSort(a, 10);
//
//	for (int i = 0; i < 10; i++) 
//	{
//		cout << a[i] << " ";
//	}
//	return 0;
//}


//
//#include"Graph.h"
//void test_Graph_Edge() 
//{
//	Adjay::Graph<char, int> ghp("abcd", 4);
//	ghp.AddEdge('a', 'b', 1);
//	ghp.AddEdge('c', 'd', 1);
//	ghp.AddEdge('d', 'b', 1);
//	ghp.AddEdge('c', 'b', 1);
//	ghp.Print();
//}
//
//void test_Graph_matrix()
//{
//
//	const char* str = "12345";
//	matrix::Graph<char, int, INT_MAX, true> g(str, strlen(str));
//	g.AddEdge('1', '2', 3);
//	g.AddEdge('1', '3', 8);
//	g.AddEdge('1', '5', -4);
//	g.AddEdge('2', '4', 1);
//	g.AddEdge('2', '5', 7);
//	g.AddEdge('3', '2', 4);
//	g.AddEdge('4', '1', 2);
//	g.AddEdge('4', '3', -5);
//	g.AddEdge('5', '4', 6);
//
//	//ghp.BFS('a');
//	//ghp.DFS('a');
//
//	matrix::Graph<char, int> mintree;
//
//	//cout << ghp.KrusKal(mintree) << endl;
//
//	//cout << ghp.Prime(mintree, 'a') << endl;
//	vector<int> dst;
//	vector<int> path;
//	vector<vector<int>> vvDist;
//	vector<vector<int>> vvParentPath;
//
//	g.FloyWarshell(vvDist, vvParentPath);
//
//	for (size_t i = 0; i < strlen(str); ++i)
//	{
//		g.PrinrtShotPath(str[i], vvDist[i], vvParentPath[i]);
//		cout << endl;
//	}
//	cout << str << endl;
//
//}


#include<iostream>
#include<iomanip>
using namespace std;
//
//void func6(int x) throw (int)
//{
//	if (x > 0) throw "异常";
//}
//
//int main()
//{
//	//double values[] = {1.23, 35.36, 653.7, 4358.24};
//	//const char* names[] = {"Zoot", "Jimmy", "Al", "Stan"};
//
//	//for (int i = 0;i < 4;i++) 
//	//{
//	//	cout << setiosflags(ios_base::left)
//	//		<< setw(6) << names[i]
//	//		<< resetiosflags(ios_base::left)
//	//		<< setw(10) << setprecision(1)
//	//		<< values[i] << endl;
//
//	//}
//
//
//	//string str;
//	//char ch = 'a';
//	//cin >> str;
//
//	//cout << " " << str << " " << endl;
//	//getline(cin, )
//	/*try 
//	{
//		func6(7);
//	}
//	catch (string str) 
//	{
//		cout << str << endl;
//	}
//	catch (...) 
//	{
//		cout << "处理异常" << endl;
//	}*/
//
//
//	return 0;
//}
//
//class A 
//{
//public:
//	int _m = 0;
//	char _ch = 0;    
//	double _d = 0;   //这个是一共16个字节
//};
//
//class B : public A
//{
//public:
//	char _ch = 0;     //这里是1.
//};
//
//class C 
//{
//public: 
//	char _c = 0;
//};
//
//int main() 
//{
//	cout << sizeof(C) << endl;//只算自己的
//	cout << sizeof(B) << endl;  //基类加上派生类的， 再有内存对齐的规则
//	cout << sizeof(A) << endl;  //只算自己的
//
//
//}


//
//class A
//{
//public:
//
//	virtual void func(int a)
//	{
//		cout << "Afunc():" << a << endl;
//	}
//
//
//private:
//	int _a = 0x11;//这里初始化使用十六进制是为了好观察
//};

//class B
//{
//public:
//	virtual void funcB() 
//	{
//		cout << "funcB" << endl;
//	}
//
//	int _b = 0x22;
//};
//
//class C : public A, public B
//{
//public:
//
//	virtual void func(int a = 3)//该func重写了父类的func. 所以C类的虚函数列表之中不会包含父类的func，只有自己这个重写了的func。
//	{
//		cout << "Cfunc()" << a << endl;
//	}
//	
//	virtual void test() {}
//
//	int c = 0x11;
//};
//
//int main()
//{
//	C c;
//	cout << sizeof(C) << endl;
//
//	return 0;
//}


//int partition(int a[], int low, int high)
//{
//	int temp = a[low];
//	while (low < high)
//	{
//		while (a[high] >= temp && low < high) high--;
//		if (low < high) a[low++] = a[high];
//
//		while (a[low] <= temp && low < high) low++;
//		if (low < high) a[high--] = a[low];
//	}
//	a [low] = temp;
//	
//	return low;
//
//}
//
//
//void QuickSort(int a[], int i, int j)
//{
//	int k;
//	if (i < j)
//	{
//		k = partition(a, i, j);
//		QuickSort(a, i, k - 1);
//		QuickSort(a, k + 1, j);
//
//	}
//}
//
//
//int main() 
//{
//	int a[10] = {1, 9, 8, 6, 5, 4, 3, 2, 7, 6};
//	QuickSort(a, 0, sizeof(a) / sizeof(a[0]) - 1);
//	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) printf("%d ", a[i]);
//	return 0;
//}



////A位基类
//class A
//{
//public:
//	int _a;
//	double _aa;
//};
//
////B类继承A类
//class B : public A
//{
//public:
//	char _b;
//};
//
//int main() 
//{
//	cout << sizeof(A) << endl;
//	cout << sizeof(B) << endl;
//
//	return 0;
//}
//
//int main() 
//{
//	char ch = 'a';
//	cout.put(ch);
//
//	char ch2 = 'b';
//	cin.get(ch2);
//	cout.put(ch2);
//
//	string str;
//	getline(cin, str);
//
//	return 0;
//}

//
//int main() 
//{
//	cout.fill('*');
//
//	for (int i = 0; i < 10; i++) 
//	{
//		cout.width(10);
//		cout << i << endl;
//	}
//
//	cout.width(10);
//	cout << "sd" << endl;
//	cout.width(11);
//	cout << "ad" << endl;
//
//	return 0;
//}

//int main() 
//{
//	cout.width(100);
//	cout << "李四" << endl;
//	cout << setw(6) << "张三" << endl;
//
//	return 0;
//}

//int main() 
//{
//	for (int i = 1; i < 8; i++) 
//	{
//			 
//		cout << setfill(' ') << setw(i)
//			 << " " << setfill('m') << setw(13 - 2 * i) 
//			 << 'm' << endl;
//			 
//	}
//
//	return 0;
//}
//
//int main() 
//{
//	//cout << setprecision(2) << 1.34 << endl;
//	//cout.precision(1);
//	//cout << 1.34 << endl;
//	//cout << 1.43 << endl;
//	//cout.fill('*');
//	//cout.width(10);
//	//cout << 1.43 << endl;
//	//cout << dec << 10 << endl;
//	//cout << oct << 20 << endl;
//	//cout << hex << 19 << endl;
//	//cout << setw(8) << 8 << endl;
//	char x = 'a';
//	char y = 'A';
//
//	cout << setiosflags(ios::showbase | ios::uppercase);
//	cout << x << ' ' << y << ' ' << endl;
//
//	return 0;
//}



//
//#include<fstream>
//
//int main() 
//{
//	ofstream ff;
//	ff.open("D://test01.txt");
//	ff << "abcdef" << endl << "kdjdfksd" << endl;
//	ff << "hello world!" << endl;
//	
//	ff.close();
//}

//#include<fstream>
//#include<istream>
//
//int main() 
//{
//	ofstream ff;
//
//	ff.open("D://test01.txt");
//	ff << "hello world!" << endl;
//	ff.close();
//
//	ff.open("D://test01.txt", ios::app);
//	ff << "这一行是追加的内容" << endl;
//	ff.close();
//
//	return 0;
//}
// 
//namespace cws 
//{
//
//	class A
//	{
//	public:
//		A(int num = 0) 
//			:_a(num)
//			,_b(num)
//		{
//		}
//		static void func(A a)
//		{
//			cout << a._a << _b << endl;
//		}
//	private:
//		int _a = 1;
//		int _b = 0;
//		static double _b;
//	};
//
//}
//
//double cws::A::_b = 1.1;     //类型 + 作用域::变量名
//
//int main() 
//{
//	cws::A a;
//	cws::A::func(a);
//	
//	return 0;
//}
//
//#include"BTree2.h"
//using namespace BTree_My;
//
//int main() 
//{
//	//test_Graph_matrix();
//	//test_Graph_Edge();
//	BTree<int, 3> bt;
//
//	bt.insert(59);
//	bt.insert(139);
//	bt.insert(75);
//	bt.insert(49);
//	bt.insert(145);
//	bt.insert(36);
//	bt.insert(11111);
//	bt.insert(8761);
//	bt.insert(9871);
//	bt.insert(1);
//	bt.insert(111);
//	bt.insert(156);
//
//
//	bt.InOrder();
//	return 0;
//
//}
//
//#include<iostream>
//#include<string>
//#include<vector>
//using namespace std;
//
//namespace school_work 
//{
//
//	class Bank_Card
//	{
//	public:
//		//构造函数， 开一个卡
//		Bank_Card(string name, string no = string(), string password = string(), double balance = 0)
//			:_name(name)
//			, _no(no)
//			, _password(password)
//		{}
//
//
//		//创建账户
//		void Set_no(string no, string password)
//		{
//			_no = no;
//			_password = password;
//		}
//
//		//取钱
//		void WithDrow(double balance)
//		{
//			if (_balance < balance)
//			{
//				cout << "余额不足" << endl;
//			}
//			_balance -= balance;
//		}
//
//		//存钱
//		void Saving(double balance)
//		{
//			_balance += balance;
//		}
//
//		//销毁账户
//		void Destroy()
//		{
//			_no = string();
//			_password = string();
//			_balance = double();
//			_name = string();
//		}
//
//		//修改密码
//		void New_Passwd()
//		{
//			string new_passwd;
//			string a_new_passwd;
//			cout << "New Passwd： ";
//			cin >> new_passwd;
//			cout << endl;
//			cout << "again New Passwd:    ";
//			cin >> a_new_passwd;
//			cout << endl;
//			if (new_passwd != a_new_passwd)
//			{
//				cout << "修改失败" << endl;
//			}
//			else
//			{
//				_password = new_passwd;
//				cout << "修改成功" << endl;
//			}
//		}
//
//		//Print
//		void Print()
//		{
//			cout << "余额为: " << _balance << endl;
//		}
//
//	private:
//		string _name;
//		string _no;
//		string _password;
//		double _balance;
//	};
//
//
//
//
//	//MP3
//	struct song 
//	{
//		song(string name = "姓名未知", string author = "作者未知")
//			:_name(name)
//			,_author(author)
//		{}
//
//		string _name;       //歌曲名称
//		string _author;     //歌曲作者
//	};
//
//
// 	class MP3 
//	{
//	public:
//
//		//构造函数
//		MP3(vector<song> MP3 = vector<song>(), int voice_level = 5, int electricity = 100)
//			:_MP3(MP3)
//			,_voice_level(voice_level)
//			,_electricity(electricity)
//		{}
//
//		//添加歌曲
//		void Add_song() 
//		{
//			string name = string();
//			string author = string();
//
//			cout << "请输入你要添加歌曲的姓名:>";
//			cin >> name;
//			cout << "请输入你要添加歌曲的作者:>";
//			cin >> author;
//			
//			song s(name, author);
//			_MP3.push_back(s);
//		}
//
//		//删除歌曲
//		void Erase_song() 
//		{
//			cout << "请输入你要删除的歌曲的名称" << endl;
//			string name = string();
//			cin >> name;
//			cout << "请输入你要删除的歌曲的作者" << endl;
//			string author = string();
//			cin >> author;
//
//			auto it = _MP3.begin();
//			while (it != _MP3.end())    //利用迭代器寻找并且删除， 直接调用vector接口，无需自己覆盖元素.
//			{
//				if (it->_name == name && it->_author == author) 
//				{
//					_MP3.erase(it);
//					cout << "已删除" << endl;
//				}
//				it++;
//			}
//			
//			cout << "未找到该歌曲" << endl;
//		}
//
//		//调高音量
//		void turn_up() 
//		{
//			if (_voice_level == _voice_max) cout << "已到最大音量" << endl;
//			else _voice_level++;
//		}
//
//		//调低音量
//		void turn_down() 
//		{
//			if (_voice_level = _voice_min) cout << "已到最小音量" << endl;
//			else _voice_level--;
//		}
//
//		//查看剩余电量
//		void Print_ele()
//		{
//			cout << "电量: " << _electricity << endl;
//		}
//
//		//播放歌曲
//		void player_song() 
//		{
//			cout << "请输入你要播放的歌曲的名称" << endl;
//			string name = string();
//			cin >> name;
//			cout << "请输入你要播放的歌曲的作者" << endl;
//			string author = string();
//			cin >> author;
//
//			auto it = _MP3.begin();
//			while (it != _MP3.end())     //利用迭代器寻找并且删除， 直接调用vector接口，无需自己覆盖元素.
//			{
//				if (it->_name == name && it->_author == author)
//				{
//					cout << "已播放" << endl;
//				}
//				it++;
//			}
//
//			cout << "未找到该歌曲" << endl;
//		}
//
//	protected:
//		const int _voice_max = 10;       //定义最大音量
//		const int _voice_min = 0;       //定义最小音量
//
//
//	private:
//		vector<song> _MP3;
//		int _voice_level;
//		int _electricity;
//	};
//
//}
//
//
//void menu() 
//{
//	cout << "******************************" << endl;
//	cout << "*****   1、播放歌曲       *****" << endl;
//	cout << "*****   2、添加歌曲       *****" << endl;
//	cout << "*****   3、删除歌曲       *****" << endl;
//	cout << "*****   4、调高音量       *****" << endl;
//	cout << "*****   5、调低音量       *****" << endl;
//	cout << "*****   6、显示电量       *****" << endl;
//	cout << "*****   0、退出程序       *****" << endl;
//	cout << "******************************" << endl;
//
//}
//
//int main() 
//{
//	school_work::MP3 mp3;
//	int input = 1;
//	while (input) 
//	{
//		menu();
//		cout << "请输入你要进行的操作>:";
//		cin >> input;
//		switch (input)
//		{
//		case 1:
//			mp3.player_song();
//			break;
//		case 2:
//			mp3.Add_song();
//			break;
//		case 3:
//			mp3.Erase_song();
//			break;
//		case 4:
//			mp3.turn_up();
//			break;
//		case 5:
//			mp3.turn_down();
//			break;
//		case 6:
//			mp3.Print_ele();
//			break;
//		case 0:
//			cout << "已退出" << endl;
//			break;
//		default:
//			cout << "非法输入" << endl;
//			break;
//		}
//	}
//
//
//	return 0;
//}
//#include<iostream>
//using namespace std;
//#include"Heap.h"
//
//int main() 
//{
//	Heap<int> hp;
//	hp.push(1);
//	hp.push(9);
//	hp.push(3);
//	hp.push(5);
//
//	cout << hp.top() << endl;
//	hp.pop();
//	cout << hp.top() << endl;
//	hp.pop();
//	cout << hp.top() << endl;
//	hp.pop();
//	cout << hp.top() << endl;
//
//	int arr[10] = { 1, 4, 2 , 5, 3, 9, 8, 6, 7, 0 };
//	HeapSort(arr, 10);
//	for (int i = 0; i < 10; i++) cout << arr[i] << "   ";
//
//
//	return 0;
//}
//
//#include"Graph.h"
//
//int main() 
//{
//	Graph::Graph<char, int, INT_MAX, true> gh("abcdefg", 7);
//	gh.insert('a', 'b', 15);
//	gh.insert('a', 'c', 2);
//	gh.insert('a', 'd', 12);
//	gh.insert('b', 'e', 6);
//	gh.insert('c', 'e', 8);
//	gh.insert('c', 'f', 4);
//	gh.insert('e', 'g', 9);
//	gh.insert('f', 'd', 5);
//	gh.insert('f', 'g', 10);
//	gh.insert('g', 'b', 4);
//	gh.insert('d', 'g', 3);
//	//gh.BFS('a');
//	//cout << endl;
//	//gh.DFS('a');
//	//vector<int> dst;
//	//vector<int> pPath;
//	//gh.BellmanFord('a', dst, pPath);
//	//gh.PrintShortPath('a', dst, pPath);
//
//	Graph::Graph<char, int, INT_MAX, true> mintree;
//	gh.Prime(mintree, 'a');
//	
//
//	mintree.Print();
//}

#include"unordered_set-6-1.h";
#include"unordered_map-6-1.h"
#include"hashtable.h"
#include<queue>
//
//int main()
//{
//	//Open_adress::Hashtables<int, int> ht;
//	//ht.insert({ 9, 1 });
//	//ht.insert({ 2, 1 });
//	//ht.insert({ 6, 1 });
//	//ht.insert({ 22, 1 });
//	//ht.insert({ 12, 1 });
//	//ht.insert({ 11, 1 });
//	//ht.insert({ 42, 1 });
//	//ht.insert({ 3, 1 });
//	//ht.insert({ 9, 1 });
//
//	//ht.insert({ 4, 1 });
//
//	//ht.Erase(4);
//
//
//	//unordered_map<int, int> hash;
//
//	//auto old = hash.bucket_count();    //大小
//
//	//for (int i = 0; i < 1000; i++) 
//	//{
//
//	//	hash.insert({ i, 1 });
//	//	if (hash.bucket_count() != old) 
//	//	{
//	//		cout << old << endl;
//	//		old = hash.bucket_count();
//	//	}
//	//}
//	//HashBucket::HashBucket<int, int> bht;
//	//bht.insert({ 91, 3 });
//	//bht.insert({ 81, 3 });
//	//bht.insert({ 71, 3 });
//	//bht.insert({ 51, 3 });
//	//bht.insert({ 41, 3 });
//	//bht.insert({ 31, 3 });
//	//bht.insert({ 121, 3 });
//	//bht.insert({ 19, 3 });
//	//bht.insert({ 17, 3 });
//	//bht.insert({ 15, 3 });
//	//bht.insert({ 13, 3 });
//	//bht.insert({ 12, 3 });
//	//bht.Erase(91);
//	//auto it = bht.Find(71);
//	//cout << it->_kv.first << endl;
//	//auto bht
//
//	//My_unordered_set::MySet<int> st;
//	//st.insert(51);
//	//st.insert(31);
//	//st.insert(21);
//	//st.insert(199);
//	//st.insert(18);
//	//st.insert(16);
//	//st.insert(14);
//	//st.insert(11);
//	//st.insert(12);
//	//st.insert(161);
//	//st.insert(1161);
//
//	//My_unordered_map::My_unordered_map<int, int> mp;
//	//mp.insert({ 18, 1 });
//	//mp.insert({ 61, 1 });
//	//mp.insert({ 11, 1 });
//	//mp.insert({ 21, 1 });
//	//mp.insert({ 31, 1 });
//	//mp.insert({ 41, 1 });
//	//mp.insert({ 51, 1 });
//	//mp.insert({ 14, 1 });
//	//mp.insert({ 12, 1 });
//	//mp.insert({ 11, 1 });
//	//mp.insert({ 13, 1 });
//	//mp.insert({ 15, 1 });
//	//mp.insert({ 111, 1 });
//
//	//queue<int> q;
//	//const int a = 5;
//	//q.push(a);
//	//q.front() = 3;
//	//int top = q.front();  //front返回的是引用。 但是这个引用为什么可以使用
//	//top = 5;
//	//cout << top << endl;
//
//
//	//My_unordered_set::test_set();
//	//cout << endl;
//	//My_unordered_map::test_map();
//
//	return 0;
//}
//
//class A 
//{
//	typedef int sss;
//
//};
//
//int main() 
//{
//	A::sss it = 1;
//}

#include"list.h"
#include"unordered_set-6-1.h";
#include"unordered_map-6-1.h"
#include"hashtable.h"
#include<queue>
//
//int main()
//{
//	//Open_adress::Hashtables<int, int> ht;
//	//ht.insert({ 9, 1 });
//	//ht.insert({ 2, 1 });
//	//ht.insert({ 6, 1 });
//	//ht.insert({ 22, 1 });
//	//ht.insert({ 12, 1 });
//	//ht.insert({ 11, 1 });
//	//ht.insert({ 42, 1 });
//	//ht.insert({ 3, 1 });
//	//ht.insert({ 9, 1 });
//
//	//ht.insert({ 4, 1 });
//
//	//ht.Erase(4);
//
//
//	//unordered_map<int, int> hash;
//
//	//auto old = hash.bucket_count();    //大小
//
//	//for (int i = 0; i < 1000; i++) 
//	//{
//
//	//	hash.insert({ i, 1 });
//	//	if (hash.bucket_count() != old) 
//	//	{
//	//		cout << old << endl;
//	//		old = hash.bucket_count();
//	//	}
//	//}
//	//HashBucket::HashBucket<int, int> bht;
//	//bht.insert({ 91, 3 });
//	//bht.insert({ 81, 3 });
//	//bht.insert({ 71, 3 });
//	//bht.insert({ 51, 3 });
//	//bht.insert({ 41, 3 });
//	//bht.insert({ 31, 3 });
//	//bht.insert({ 121, 3 });
//	//bht.insert({ 19, 3 });
//	//bht.insert({ 17, 3 });
//	//bht.insert({ 15, 3 });
//	//bht.insert({ 13, 3 });
//	//bht.insert({ 12, 3 });
//	//bht.Erase(91);
//	//auto it = bht.Find(71);
//	//cout << it->_kv.first << endl;
//	//auto bht
//
//	//My_unordered_set::MySet<int> st;
//	//st.insert(51);
//	//st.insert(31);
//	//st.insert(21);
//	//st.insert(199);
//	//st.insert(18);
//	//st.insert(16);
//	//st.insert(14);
//	//st.insert(11);
//	//st.insert(12);
//	//st.insert(161);
//	//st.insert(1161);
//
//	//My_unordered_map::My_unordered_map<int, int> mp;
//	//mp.insert({ 18, 1 });
//	//mp.insert({ 61, 1 });
//	//mp.insert({ 11, 1 });
//	//mp.insert({ 21, 1 });
//	//mp.insert({ 31, 1 });
//	//mp.insert({ 41, 1 });
//	//mp.insert({ 51, 1 });
//	//mp.insert({ 14, 1 });
//	//mp.insert({ 12, 1 });
//	//mp.insert({ 11, 1 });
//	//mp.insert({ 13, 1 });
//	//mp.insert({ 15, 1 });
//	//mp.insert({ 111, 1 });
//
//	//queue<int> q;
//	//const int a = 5;
//	//q.push(a);
//	//q.front() = 3;
//	//int top = q.front();  //front返回的是引用。 但是这个引用为什么可以使用
//	//top = 5;
//	//cout << top << endl;
//
//
//	//My_unordered_set::test_set();
//	//cout << endl;
//	//My_unordered_map::test_map();
//
//	cws_list::test_list();
//
//	return 0;
//}


//class Solution
//{
//public:
//    int evalRPN(vector<string>& tokens)
//    {
//        stack<int> st;
//        int index = 0;
//
//        while (index < tokens.size())
//        {
//            string str = tokens[index];
//            index++;
//
//            if (str[0] == '+' || str[0] == '-' || str[0] == '*' || str[0] == '/')
//            {
//                int right = st.top();
//                st.pop();
//                int left = st.top();
//                st.pop();
//                switch (str[0])
//                {
//                case '+':
//                    st.push(left + right);
//                    break;
//                case '-':
//                    st.push(left - right);
//                    break;
//                case '*':
//                    st.push(left * right);
//                    break;
//                case '/':
//                    st.push(left / right);
//                    break;
//                }
//
//            }
//            else
//            {
//                st.push(stoi(str));
//            }
//        }
//        return st.top();
//    }
//};

//
//int main() 
//{
//    vector<string> str;
//    //"2","1","+","3","*"
//    str.push_back("2");
//    str.push_back("1");
//    str.push_back("+");
//    str.push_back("3");
//    str.push_back("*");
//
//    Solution sol;
//    int a= sol.evalRPN(str);
//
//    cout << a << endl;
//}

//#include"Container.h"
//#include"functional_test.h"
//int main() 
//{
//
//	cws_Container::test_priority();
//	cout << endl << endl;
//	cws_functional_test::test_functional();
//
//	return 0;
//}



//stl源码剖析--适配器章节
//int main() 
//{

//}


//void swap1(int& x, int& y) 
//{
//	int tmp = x;
//	x = y;
//	y = tmp;
//}
//
//int main() 
//{
//	//cws_function_adaptor::test4();
//	//cws_iterator_adaptor::test1();
//	//cws_function_adaptor::test1();
//	//cws_function_adaptor::test5();
//
//
//
//	//int a = 0;
//	//cin >> a;
//	//cout << a << endl;
//	//scanf("%c", &a);
//	//cout << a << endl;
//	//cout << swap1 << endl;
//	//if (cin)
//	//{
//	//	cout << " 111 " << endl;
//	//}
//	//int da;
//	//cin >> da;
//	//if (cin)
//	//{
//	//	cout << "adf" << endl;
//	//}
//
//	//cws_iterator_adaptor::test2();
//	//cws_function_adaptor::test6();
//	//cws_function_adaptor::test7();
//	//cws_function_adaptor::test8();
//	//cws_function_adaptor::test9();
//	//cws_function_adaptor::test10();
//	//cws_function_adaptor::test11();
//	//cws_function_adaptor::test12()/*;*/
//	//cws_function_adaptor::test13();
//	//cws_function_adaptor::test14();
//	//cws_function_adaptor::test15();
//	//cws_function_adaptor::test16();
//	//cws_function_adaptor::test18();
//
//
//}
//
//


#include<iterator>   //for iterator adapters。使用迭代器的适配器
#include<functional>
#include<algorithm>
#include<iostream>
#include"Adaptor.h"
#include<set>
#include"Adaptor_blog.h"
using namespace std;
#include"School_Sort.h"
#include"Special_Desigh.h"
#include"School_Graph.h"
#include"bitset-6-18.h"
#include"rb_tree-6-18.h"
#include"set-6-19.h"
#include"map-6-19.h"
#include"fstream-6-20.h"
#include"bitset-6-20.h"
#include"share_ptr.h"
//int main() 
//{
	//blog_cws_Adaptor::test1();

	//list<int> l1;
	//blog_Adaptor::front_inserter(l1) = blog_Adaptor::front_inserter(l1) = 1;
	
	//cws_School_Sort::test_Bullon();
	//cws_School_Sort::test_Select();

	//cws_special_design::test2();
	//school_test::test();
	//cws_bitset::test1();
	//cws_rb_tree::test();
	//cws_set::test();
	//cws_map::test();
	//cws_fstream::test1();
	//cws_bit_data::test();
	//cws_RAII::test();
//}

//void func() 
//{
//	int* p = new int;
//}
//
//int main() 
//{
//	func();
//
//	return 0;
//}
//
//template<class T>
//class Smart_ptr
//{
//public:
//	Smart_ptr(T* ptr)   //智能指针构造
//		:_ptr(ptr)
//	{
//		cout << "Smart_ptr()" << endl;
//	}
//	//
//	~Smart_ptr()         //析构函数
//	{
//		cout << "~Smart_ptr()" << endl;
//		delete _ptr;
//	}
//
//	T& operator*()       //相当于指针的解引用
//	{
//		return *_ptr;
//	}
//
//	T* operator->()      //相当于指针的->操作
//	{
//		return _ptr;
//	}
//
//private:
//	T* _ptr;      //成员变量是维护一份资源的指针。
//};
//
//
//void func() 
//{
//	Smart_ptr<int> p = new int;
//	*p = 4;
//}

//int main() 
//{
//	//func();
//	//cws_School_Sort::test_Select();
//	//cws_School_Sort::test_Bullon();
//	return 0;
//}
//
//void test() 
//{
//	int* ptr = new int;
//
//	if (1) 
//	{
//		throw "发生异常";     //这里发生截胡， 无法走到下一行。
//	}
//	delete ptr;          //这里没有释放资源
//}
//
//
//int main() 
//{
//	try 
//	{
//		test();
//	}
//	catch (const char* str)
//	{
//		cout << str << endl;
//	}
//	catch (...) 
//	{
//		cout << "未知异常" << endl;
//	}
//	return 0;
//}
//
//#include<memory>             //只用智能指针需要包含memory头文件
//
//int main() 
//{
//	auto_ptr<int> p(new int);                  //利用auto_ptr创建一个管理int指针资源的对象
//	
//
//	int* tmp = p.get();
//	cout << tmp << endl;
//
//	return 0;
//}


//#include<memory>             //只用智能指针需要包含memory头文件
//
//int main()
//{
//	auto_ptr<int> p(new int);                  //利用auto_ptr创建一个管理int指针资源的对象
//
//	int* begin = p.get();
//	cout << begin << endl;
//	
//	p.reset(new int);         //重新获得资源
//	int* end = p.get();
//	cout << end << endl;
//
//
//
//	return 0;
//}

//#include<memory>             //只用智能指针需要包含memory头文件
//
//int main()
//{
//	int* a = new int;
//
//	shared_ptr<int> p1(a);       //构造函数
//	shared_ptr<int> p2(p1);      //拷贝构造
//	cout << p1.use_count() << endl;
//	cout << p2.use_count() << endl;
//
//	shared_ptr<int> p3(p2);
//	cout << p3.use_count() << endl;
//	cout << p2.use_count() << endl;
//	cout << p1.use_count() << endl;
//	shared_ptr<int[]> p(new int[5]{ 1, 2, 3, 4, 5 });      //C++17后支持
//	cout << p.use_count() << endl;
//	return 0;
//}

//#include<memory>             //只用智能指针需要包含memory头文件
//#include"share_ptr.h"
//struct chicken;
//
//struct fish 
//{
//	cws_RAII::shared_ptr<chicken> _chicken;
//};
//
//struct chicken
//{
//	cws_RAII::shared_ptr<fish> _fish;
//};


//
//int main()
//{
//	//shared_ptr<int> p = make_shared<int>(1);
//	//cout << p.use_count() << endl;
//
//	//int* a = new int;
//	//shared_ptr<int> p1(a);
//	//shared_ptr<int> p2(a);
//
//	cws_RAII::shared_ptr<fish> f1(new fish);
//	cws_RAII::shared_ptr<chicken> c1(new chicken);
//
//
//	//(*f1)._chicken = c1;
//	//(*c1)._fish = f1;
//	//
//	shared_ptr<fish> f2(new fish);
//
//	weak_ptr<fish> f3(f2);     //将一个shared_ptr给给f3
//	f3 = f2;                   //将shared_ptr赋值给weak_ptr
//	f2 = f3.lock();            //将一个weak_ptr使用lock接口转化为shared_ptr;                   
////	return 0;
////}
//
//int main() 
//{
//	//shared_ptr<int> s1(new int);
//	//(*s1) = 10;
//	//weak_ptr<int> w1(s1);
//	//cout << w1.use_count() << endl;
//
//
//	//shared_ptr<int[]> arr(new int[6] { 1, 2, 3, 4, 5, 6 }, [](int* ptr) { delete[] ptr;});     //将一块数组托管, 使用定制删除器
//	//shared_ptr<FILE> f1(fopen("data.txt", "r"), [](FILE* f) { fclose(f);});    //前提是要有data.txt这个文件
//
//	int a = 10;
//	int& b;
//	cout
//
//
//	return 0;
//}

//int main()
//{
//	int k = 0;
//	cin >> k;
//	int n = 3;
//	vector<int> v(n);
//	while (k--) 
//	{
//		for (int i = 0; i < 3; i++) 
//		{
//			cin >> v[i];
//		}
//		//
//		for (int j = 0; j < 5; j++) 
//		{
//			int min = 0;
//			for (int i = 0; i < 3; i++) 
//			{
//				if (v[i] < v[min]) 
//				{
//					min = i;
//				}
//			}
//			v[min]++;
//		}
//
//		int ret = 1;
//		for (int i = 0; i < 3; i++) 
//		{
//			ret *= v[i];
//		}
//		cout << ret << endl;
//	}
//
//	return 0;
//}
//
//int main() 
//{
//	int t = 0;
//	cin >> t;
//	while (t--) 
//	{
//		int n = 0;
//		int k = 0;
//		cin >> n >> k;
//		vector<int> v(k);
//		int max = 0;
//		for (int i = 0; i < k; i++) 
//		{
//			cin >> v[i];
//			if (v[i] > v[max])
//			{
//				max = i;
//			}
//		}
//
//		int count = 0;
//		for (int i = 0; i < k; i++) 
//		{
//			if (i != max) 
//			{
//				count += v[i] - 1;
//				count += v[i];
//			}
//		}
//	
//		cout << count << endl;
//	}
//	return 0;
//}


#include<iostream>
using namespace std;
#include<vector>
#include<queue>
//
//int path = 0;
//int ret = 0;
//vector<bool> check;
//void dfs(vector<int>& arr, int i)
//{
//	int tmp = arr[i];
//	if (check[tmp] == true) return;
//	check[tmp] = true;
//	path++;
//	dfs(arr, tmp);
//}
//
//int main()
//{
//	int n = 0;
//	cin >> n;
//	vector<int> arr(n);
//	for (int i = 0; i < n; i++)
//	{
//		cin >> arr[i];
//
//	}
//	for (int i = 0; i < n; i++)
//	{
//		check.resize(n, false);
//		check[i] = true;
//		path = 1;
//		dfs(arr, i);
//		ret = max(ret, path);
//	}
//
//	cout << ret << endl;
//
//	return 0;
//}

#include<iostream>
using namespace std;
#include<vector>

//
//int main() 
//{
//	int k = 0;
//	cin >> k;
//
//	while (k--) 
//	{
//		int n, m;
//		cin >> n >> m;
//		vector<vector<int>> ver(n, vector<int>(m, 0));
//
//		for (int i = 0; i < n; i++) 
//		{
//			for (int j = 0; j < m; j++) 
//			{
//				cin >> ver[i][j];
//			}
//		}
//
//		if (n == 1 && m == 1) 
//		{
//			cout << -1 << endl;
//			continue;
//		}
//		else 
//		{
//			int key = ver[0][0];
//			for (int i = 0; i < n; i++)
//			{
//				if (i > 0) 
//				{
//					ver[i - 1][m - 1] = ver[i][0];
//				}
//				int end = 0;
//				while (end < m - 1) 
//				{
//					ver[i][end] = ver[i][end + 1];
//					end++;
//				}
//			}
//			ver[n - 1][m - 1] = key;
//
//		}
//
//		for (int i = 0; i < n; i++)
//		{
//			for (int j = 0; j < m; j++) 
//			{
//				cout << ver[i][j] << " ";
//			}
//			cout << endl;
//		}
//
//	}
//
//	
//
//	return 0;
//}

//
//#include<iostream>
//using namespace std;
//#include<vector>
//
//int main()
//{
//	int k = 0;
//	cin >> k;
//	while (k--) 
//	{
//		long long n, x;
//		cin >> n >> x;
//		vector<long long> arr(n);
//		long long count = 0;
//		int sum2 = 0;
//		for (long long i = 0; i < n; i++) 
//		{
//			scanf("%d", &arr[i]);
//			sum2 += arr[i];
//			if (sum2 > x) 
//			{
//				sum2 = 0;
//			}
//			else 
//			{
//				count++;
//			}
//		}
//
//		long long left = 0;
//		long long right = 0;
//		for (long long left = 1; left < n; left++) 
//		{
//			long long sum = 0;
//			for (long long right = left; right < n; right++) 
//			{
//				sum += arr[right];
//				if (sum > x) 
//				{
//					sum = 0;
//				}
//				else 
//				{
//					count++;
//				}
//			}
//		}
//		cout << count << endl;
//	}
//
//	return 0;
//}
//

//
//int main() 
//{
//	int s;
//	cin >> s;
//	s %= 100;
//	cout << 100 - s << endl;
//	return 0;
//}


//#include<iostream>
//using namespace std;
//#include<vector>
//#include<algorithm>
//int main() 
//{
//	int n, m, k;
//	cin >> n >> m >> k;
//	vector<int> arr(n);
//	for (int i = 0; i < n; i++) 
//	{
//		cin >> arr[i];
//	}
//	//
//	sort(arr.begin(), arr.end());
//	int index = n - k;
//	cout << m - arr[index] << endl;
//	
//	return 0;
//}


//int main() 
//{
//	int t = 0;
//	cin >> t;;
//	while (t--) 
//	{
//		int n = 0;
//		int k = 0;
//		cin >> n >> k;
//
//		int sum = 2 * n - 1;
//		int ret = 0;
//		if (k == 0) 
//		{
//			cout << 0 << endl;
//			continue;
//		}
//		else if (k < n) 
//		{
//			cout << 1 << endl;
//			continue;
//		}
//		else 
//		{
//			ret = 1;
//			k -= n;
//			n--;
//			while (n > 0 && (k - 2 * n) > 0)
//			{
//				k -= 2 * n;
//				n--;
//				ret += 2;
//			}
//			if (n == 0) cout << ret << endl;
//			else
//			{
//				if (k == 0)
//				{
//					cout << ret << endl;
//				}
//				else if (k - n <= 0) 
//				{
//					cout << ret + 1 << endl;
//				}
//				else 
//				{
//					cout << ret + 2 << endl;
//				}
//			}
//			continue;
//		}
//
//
//	}
//	return 0;
//}
//




//
//int main() 
//{
//	int t = 0;
//	cin >> t;
//	while (t--) 
//	{
//		long long n, m;
//		cin >> n >> m;
//		vector<long long> arr(n);
//		for (long long i = 0; i < n; i++) 
//		{
//			cin >> arr[i];
//		}
//
//		sort(arr.begin(), arr.end(), greater<long long>());
//
//		//降序排列
//		long long left = 0;
//		long long right = 0;
//		while (arr[left] > m)
//		{
//			left++;
//		}
//		while (arr[right] > m)
//		{
//			right++;
//		}
//
//		long long tmp = 0;
//		long long ret = 0;
//		while (right < n) 
//		{
//			while (tmp + arr[right] > m || arr[left] - arr[right] > 1)
//			{
//				tmp -= arr[left];
//				left++;
//			}
//			tmp += arr[right];
//			ret = max(tmp, ret);
//			right++;
//		}
//		cout << ret << endl;
//	}
//	return 0;
//}


#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>
#include<functional>

class UnionFind
{
public:

	//合并并查集， 如果两个节点所属不同集合， 那么就要合并两个节点的根节点。 
	void Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);
		if (root1 == root2) return;

		_ufs[root1] += _ufs[root2];
		_ufs[root2] = root1;
	}

	//并查集查找根节点
	int FindRoot(int x)
	{
		int parenti = x;
		while (_ufs[parenti] >= 0)
		{
			parenti = _ufs[parenti];
		}

		return parenti;
	}

	bool IsSet(int x1, int x2)  //判断是否在一个集合
	{
		return FindRoot(x1) == FindRoot(x2);
	}

	size_t size() //集合个数
	{
		int size = 0;
		for (int i = 0; i < _ufs.size(); i++)
		{
			if (_ufs[i] < 0) size++;
		}

		return size;
	}

	UnionFind(int n)
	{
		_ufs.resize(n, -1);
	}

private:
	vector<int> _ufs;
};

#include<string.h>
//
//
//int main()
//{
//	int n = 0;
//	string str;
//	cin >> n >> str;
//	int ret = 0;
//	size_t pos = 0;
//	pos = str.find("chuan", pos);
//	while (pos != string::npos) 
//	{
//		ret++;
//		pos = str.find("chuan", pos + 5);
//	}
//
//	cout << ret << endl;
//	return 0;
//}


#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>
#include<functional>
//
//int main() 
//{
//	int t = 0;
//	cin >> t;
//	while (t--) 
//	{
//		string str1;
//		string str2;
//		cin >> str1 >> str2;
//		reverse(str1.begin(), str1.end());
//		reverse(str2.begin(), str2.end());
//		vector<int> tmp(str1.size() + str2.size() - 1);
//		for (int i = 0; i < str1.size(); i++) 
//		{
//			for (int j = 0; j < str2.size(); j++)
//			{
//				tmp[i + j] += (str1[i] - '0') * (str2[j] - '0');
//			}
//		}
//		//
//		int k = 0;
//		int cur = 0;
//		string ret;
//		while (k != 0 || cur < tmp.size()) 
//		{
//			if (cur < tmp.size()) k += tmp[cur];
//			ret += k % 10 + '0';   //ret加上k模上10
//			k /= 10;
//			cur++;
//		}
//		while (ret.size() > 1 && ret.back() == '0') ret.pop_back();
//		reverse(ret.begin(), ret.end());
//		cout << ret << endl;
//
//	}
//	return 0;
//}
//
//int main()
//{
//	int n;
//	cin >> n;
//	vector<vector<string>> book(n);
//	unordered_map<string, vector<int>> name_index;   //用来存放相同名字的书
//	int i = 0;
//	string str;
//	cin >> str;
//	name_index[str].push_back(0);
//	while (i < n)
//	{
//		book[i].push_back(str);
//		cin >> str;
//		if (!isdigit(str[0]))   //如果不是数字， 那么就新开一个书册
//		{
//			i++;
//			name_index[str].push_back(i);
//			continue;
//		}
//	}
//	//所有书册建立完毕
//
//
//
//
//	return 0;
//}


#include<iostream>
using namespace std;
#include<string>
#include<vector>
#include<unordered_map>

//int main() 
//{
//	int t = 0;
//	cin >> t;
//	while (t--) 
//	{
//		int n = 0;
//		cin >> n;
//
//		int count = 0;
//		while (n) 
//		{
//			if (n >= 4) 
//			{
//				int k = n / 4;
//				count += k;
//				n %= 4;
//				continue;
//			}
//			else 
//			{
//				count += 1;
//				n %= 2;
//			}
//		}
//		cout << count << endl;
//	}
//	return 0;
//}



//
//int main() 
//{
//	int t = 0;
//	cin >> t;
//
//	while (t--) 
//	{
//		int n, k;
//		cin >> n >> k;
//		vector<vector<int>> v(n / k, vector<int>(n / k));
//		for (int i = 0; i < n; i++) 
//		{
//			string str; 
//			cin >> str;
//			for (int j = 0; j < n; j++) 
//			{
//				if ((i) % k == 0 && (j) % k == 0)
//				{
//					v[((i) / k)][((j) / k)] = str[j] - '0';
//				}
//
//			}
//		}
//
//		for (int i = 0; i < n / k; i++) 
//		{
//			for (int j = 0; j < n / k; j++) 
//			{
//				cout << v[i][j];
//			}
//			cout << endl;
//		}
//
//
//	}
//
//
//	return 0;
//}




#include<iostream>
using namespace std;
#include<string>
#include<vector>
#include<unordered_map>
//int main() 
//{
//	int t = 0;
//	cin >> t;
//	while (t--) 
//	{
//		int n, q;
//		cin >> n >> q;
//
//		string a;
//		string b;
//		cin >> a >> b;
//		while (q--)
//		{
//			int l, r;
//			cin >> l >> r;
//
//			unordered_map<char, int> mp1;
//
//			for (int i = l - 1; i < r; i++) mp1[a[i]]++;
//			for (int i = l - 1; i < r; i++) mp1[b[i]]--;
//
//			int count = 0;
//			for (auto e : mp1) 
//			{
//				count += abs(e.second);
//			}
//			cout << count / 2 << endl;
//
//		}
//
//
//	}
//	return 0;
//}
//
//int main() 
//{
//	int t = 0;
//	cin >> t;
//	while (t--)
//	{
//		int n, x;
//		cin >> n >> x;
//		long long ret = 0;
//		for (int c = x - 2; c >= 1; c--) 
//		{
//			int a = 1;
//			int b = x - c - a;
//
//			if (b > c) b = c;
//			while (a <= b)
//			{
//				if (a * b + a * c + b * c <= n && a + b + c <= x)
//				{
//					if (b == c)
//					{
//						if (b == c && b == a) ret += 1;
//						else ret += (long long)(b - a - 1) * 6 + 6;
//					}
//					else
//					{
//						ret += (b - a) * 6 + 3;
//					}
//					a++;
//				}
//				else
//				{
//					b--;
//				}
//			}
//
//		}
//
//		cout << ret << endl;
//	}
//	return 0;
//}


#include<iostream>
using namespace std;

#include<string>
#include<vector>

//int main() 
//{
//
//	int n = 0;
//	cin >> n;
//	vector<string> vs;
//	for (int i = 0; i < n; i++) 
//	{
//		string tmp;
//		cin >> tmp;
//		vs.push_back(tmp);
//	}
//
//	//
//	for (int i = 1; i < n; i++) 
//	{
//		if (vs[i - 1] == "sweet" && vs[i] == "sweet" && i != n - 1) 
//		{
//			cout << "No" << endl;
//			return 0;
//		}
//		
//	}
//	cout << "Yes" << endl;
//
//	return 0;
//}

#include<iostream>
using namespace std;
#include<vector>
#include<string>

//int main() 
//{
//	int H, W;
//	cin >> H >> W;
//	
//	int i, j;
//	cin >> i >> j;
//	i -= 1;
//	j -= 1;
//	vector<vector<char>> arr(H, vector<char>(W));
//	for (int l = 0; l < H; l++) 
//	{
//		for (int k = 0; k < W; k++) 
//		{
//			cin >> arr[l][k];
//		}
//	}
//
//	string str;
//	cin >> str;
//
//	for (int k = 0; k < str.size(); k++) 
//	{
//		if (str[k] == 'L') if (j > 0 && arr[i][j - 1] != '#') j -= 1;
//		if (str[k] == 'R') if (j < W - 1 && arr[i][j + 1] != '#') j += 1;
//		if (str[k] == 'U') if (i > 0 && arr[i - 1][j] != '#') i -= 1;
//		if (str[k] == 'D') if (i < H - 1 && arr[i + 1][j] != '#') i += 1;
//
//	}
//	//
//	cout << i + 1 << " " << j + 1 << endl;
//
//	return 0;
//}



//typedef pair<int, int> PII;
//struct Compare1 
//{
//	bool operator()(PII& val1, PII& val2)
//	{
//		return val1.first > val2.first;
//	}
//
//};
//
//struct Compare2
//{
//	bool operator()(PII& val1, PII& val2)
//	{
//		return val1.second > val2.second;
//	}
//
//};
//
//
//int main() 
//{
//	int N = 0;
//	long long X, Y;
//	cin >> N >> X >> Y;
//	vector<PII> dish(N);
//	for (int i = 0; i < N; i++) cin >> dish[i].first;
//	for (int i = 0; i < N; i++) cin >> dish[i].second;
//	Compare1 com1;
//	Compare2 com2;
//
//	sort(dish.begin(), dish.end(), com1);
//	
//	long long ret1 = 0;
//	long long maxv = 0;
//	for (int i = 0; i < N; i++) 
//	{
//		maxv += dish[i].first;
//		if (maxv <= X) ret1 += 1;
//		else
//		{
//			ret1 += 1;
//			break;
//		}
//	}
//	sort(dish.begin(), dish.end(), com2);
//
//	long long ret2 = 0;
//	maxv = 0;
//	for (int i = 0; i < N; i++)
//	{
//		maxv += dish[i].second;
//		if (maxv <= Y) ret2 += 1;
//		else 
//		{
//			ret2 += 1;
//			break;
//		}
//	}
//
//
//	cout << min(ret1, ret2);
//	return 0;
//}



//
//int main()
//{
//	int t = 0;
//	cin >> t;
//	while (t--) 
//	{
//		int n = 0;
//		cin >> n;
//		int maxi = INT_MIN;
//		for (int i = 0; i < n; i++)
//		{
//			int tmp = 0;
//			cin >> tmp;
//			if (i % 2 == 0 && tmp > maxi)
//			{
//				maxi = tmp;
//			}
//		}
//		cout << maxi << endl;;
//	}
//
//	return 0;
//}
//int main() 
//{
//	int t = 0;
//	cin >> t;
//	while (t--) 
//	{
//		int n = 0;
//		cin >> n;
//		vector<int> b(n - 1);
//		vector<int> a(n);
//		for (int i = 0; i < n - 1; i++) 
//		{
//			cin >> b[i];
//			if (i == 0) a[i] = b[i];
//			else 
//			{
//				a[i] = b[i - 1] | b[i];
//			}
//		}
//		a[n - 1] = b[n - 2];
//		//
//		int flag = 1;
//		for (int i = 0; i < n - 1; i++) 
//		{
//			if (b[i] != (a[i] & a[i + 1])) flag = 0;
//		}
//		if (flag == 0) 
//		{
//			cout << -1 << endl;
//		}
//		else 
//		{
//			for (int i = 0; i < n; i++) cout << a[i] << " ";
//			cout << endl;
//		}
//
//	}
//	return 0;
//}


//#include<iostream>
//using namespace std;
//#include<vector>
//#include<string>
//#include<algorithm>
//
//
//
//int main() 
//{
//	int t = 0;
//	cin >> t;
//	while (t--) 
//	{
//		string s;
//		cin >> s;
//		if (s.size() == 1) 
//		{
//			for (char ch = 'a'; ch <= 'z'; ch++)
//			{
//				if (ch != s[0])
//				{
//					cout << s << ch << endl;
//					break;
//				}
//			}
//			continue;
//		}
//
//
//		int cur = 0;
//
//		while (cur < s.size() - 1) 
//		{
//			if (s[cur] == s[cur + 1]) break;
//			cur++;
//		}
//
//
//		cout << s.substr(0, cur + 1);
//		for (char ch = 'a'; ch <= 'z'; ch++) 
//		{
//			if (ch != s[cur]) 
//			{
//				cout << ch;
//				break;
//			}
//		}
//		cout << s.substr(cur + 1, s.size()) << endl;
//
//	}
//
//
//	return 0;
//}


//int main() 
//{
//	int t = 0;
//	cin >> t;
//	while (t--) 
//	{
//		int n = 0;
//		cin >> n;
//		vector<string> ver(2);
//		int count = 0;
//		for (int i = 0; i < 2; i++) 
//		{
//			cin >> ver[i];
//		}
//		for (int i = 0; i < 2; i++) 
//		{
//			for (int j = 0; j < n; j++) 
//				if (ver[i][j] == '.') count++;
//		}
//		//
//		if (count < 4) 
//		{
//			std::cout << 0 << endl;
//			continue;
//		}
//		else 
//		{
//			int ret = 0;
//			for (int i = 0; i < n; i++)
//			{
//				if (ver[0][i] == '.') 
//				{
//
//					if (i - 1 >= 0 && i + 1 < n) 
//					{
//						if (ver[1][i - 1] == 'x' && ver[1][i + 1] == 'x' && ver[1][i] == '.' && ver[0][i - 1] == '.' && ver[0][i + 1] == '.') ret++;
//					}
//				}
//			}
//			//
//			for (int i = 0; i < n; i++) 
//			{
//				if (ver[1][i] == '.')
//				{
//
//					if (i - 1 >= 0 && i + 1 < n)
//					{
//						if (ver[0][i - 1] == 'x' && ver[0][i + 1] == 'x' && ver[0][i] == '.' && ver[1][i - 1] == '.' && ver[1][i + 1] == '.') ret++;
//					}
//				}
//			}
//			std::cout << ret << endl;
//			continue;
//		}
//
//
//	}
//	return 0;
//}
//

//#include<iostream>
//using namespace std;
//#include<vector>
//#include<string>
//#include<algorithm>
//
//
//
//
//#include<stack>
//
//
//int main() 
//{
//	int t = 0;
//	cin >> t;
//	while (t--) 
//	{
//		int n = 0;
//		cin >> n;
//		string str;
//		cin >> str;
//		int left = 0;
//		int right = 0;
//		for (int i = 0; i < n; i++) 
//		{
//			if (str[i] == '(') left++;
//			else right++;
//		}
//		//
//		int ret = 0;
//		stack<char> st;
//		for (int i = 0; i < n; i++) 
//		{
//			if (i % 2 == 0) 
//			{
//				if (!st.size()) 
//				{
//					str[i] = '(';
//					right--;
//				}
//				else 
//				{
//					if (left > 0) 
//					{
//						str[i] = ')';
//						left--;
//					}
//					else 
//					{
//						str[i] = '(';
//						right--;
//					}
//				}
//			}
//			if (str[i] == '(') st.push(str[i]);
//			else 
//			{
//				ret += 2 * st.size() - 1;
//				st.pop();
//			}
//		}
//		cout << ret << endl;
//
//
//	}
//	return 0;
//}
//
//

//
//int main()
//{
//	int n = 0;
//	cin >> n;
//	int ret = 0;
//	while (n--)
//	{
//		string str;
//		cin >> str;
//		int cur = 0;
//		int flag = 1;
//		while (cur < str.size())
//		{
//			string tmp;
//			int cur2 = 0;
//			cur2 = str.find('.', cur);
//			if (cur2 == -1) 
//			{
//				tmp = str.substr(cur, str.size() - cur);
//				cur = str.size();
//			}
//			else 
//			{
//				tmp = str.substr(cur, cur2 - cur);
//				cur = cur2 + 1;
//			}
//			int k = stoi(tmp);
//			if (k < 0 || k > 255) flag = 0;
//		}
//
//		if (flag == 1) ret++;
//	}
//	cout << ret << endl;
//	return 0;
//}

//#include<iostream>
//using namespace std;
//#include<vector>
//#include<string>
//
//int main()
//{
//	int N, m;
//	cin >> N >> m;
//	vector<vector<int>> ker(N, vector<int>(N));
//	for (int i = 0; i < N; i++)
//	{
//		for (int j = 0;j < N; j++)
//		{
//			cin >> ker[i][j];
//		}
//	}
//	//
//	vector<vector<int>> ver(m, vector<int>(m));
//	for (int i = 0; i < m; i++)
//	{
//		for (int j = 0; j < m; j++)
//		{
//			cin >> ver[i][j];
//		}
//	}
//	vector<vector<int>> dp(m - N + 1, vector<int>(m - N + 1));
//	int u = 0, n = u + N - 1;
//
//	for (;n < m; u++, n++)
//	{
//		int l = 0, r = l + N - 1;
//		for (; r < m; l++, r++)
//		{
//			int tmp = 0;
//			//计算和
//			for (int i = 0; i < N; i++)
//			{
//				for (int j = 0; j < N; j++)
//				{
//					tmp += ver[i + u][j + l] * ker[i][j];
//				}
//			}
//
//			dp[u][l] = tmp;
//		}
//	}
//	for (int i = 0; i < m - N + 1; i++)
//	{
//		for (int j = 0; j < m - N + 1; j++)
//		{
//			cout << dp[i][j] << " ";
//		}
//		cout << endl;
//	}
//	return 0;
//}

//
//
//int main() 
//{
//	int m, n, q;
//	cin >> m >> n >> q;
//	unordered_map<string, string> keys;
//	for (int i = 0; i < m; i++) 
//	{
//		string key;
//		string val;
//		cin >> val >> key;  //先输入公钥， 在输入私钥
//		keys[key] = val;    //私钥是key， 公钥是val
//	}
//	//
//	unordered_map<string, unordered_map<string, int>> name_IP;
//	unordered_map<string, unordered_map<string, unordered_map<string, int>>> name_IP_keys;
//	for (int i = 0; i < n; i++) 
//	{
//		string IP;
//		cin >> IP;    //
//		int k;
//		cin >> k;
//		for (int j = 0; j < k; j++)
//		{
//			//k个用户
//			string usr;
//			cin >> usr;
//			name_IP[usr][IP] = 1;      //将用户与IP建立映射关系
//			int t = 0;
//			cin >> t;
//			while (t--)
//			{
//				string key;
//				cin >> key;
//				name_IP_keys[usr][IP][key] = 1;
//			}
//		}
//	}
//
//	//
//	while (q--) 
//	{
//		string usr;
//		cin >> usr;
//		string ip;
//		cin >> ip;
//		string key;
//		cin >> key;
//		string val = keys[key];    //私钥对应的公钥;
//		if (name_IP[usr][ip] == 1 && name_IP_keys[usr][ip][val] == 1)
//		{
//			cout << "Yes" << endl;
//		}
//		else 
//		{
//			cout << "No" << endl;
//		}
//	}
//
//	return 0;
//}
//
//int main() 
//{
//
//	int arr[1000010] = { 0 };
//
//	int cur = 2;
//	arr[0] = 1;
//	arr[1] = 2;
//	arr[2] = 4;
//	int t = 0;
//	cin >> t;
//	while (t--) 
//	{
//		int n = 0;
//		cin >> n;
//		if (arr[n] != 0) cout << arr[n] << " ";
//		else 
//		{
//			for (; cur <= n; cur++) 
//			{
//				arr[cur] = arr[cur - 1] + 2 * (cur - 1);
//			}
//			
//			cout << arr[n] << " ";
//		}
//	}
//	
//	return 0;
//}
//
//
//
//int main() 
//{
//
//	int t = 0;
//	cin >> t;
//	while (t--) 
//	{
//		int n = 0;
//		cin >> n;
//		if (n == 0) cout << 1 << " ";
//		else if (n == 1) cout << 2 << " ";
//		else if (n == 2) cout << 4 << " " ;
//		else cout << 2 + n * (n - 1) << " ";
//	}
//	
//	return 0;
//}
//



//
//int main() 
//{
//	int n;
//	cin >> n;
//	string str;
//	cin >> str;
//	vector<int> f(n);
//	vector<int> g(n);
//	f[0] = 1;   //第一局赢了
//	g[0] = 0;   //第一局平了
//
//	for (int i = 1; i < n; i++)
//	{
//		if (str[i - 1] == str[i]) 
//		{
//			f[i] = g[i - 1] + 1;
//		}
//		else if ((str[i - 1] == 'P' && str[i] == 'R')
//				|| (str[i - 1] == 'R' && str[i] == 'S')
//				|| (str[i - 1] == 'S' && str[i] == 'P'))
//		{
//			f[i] = f[i - 1] + 1;
//		}
//		else 
//		{
//			f[i] = max(f[i - 1], g[i - 1]) + 1;
//		}
//
//		if ((str[i - 1] == 'P' && str[i] == 'S')
//			|| (str[i - 1] == 'S' && str[i] == 'R')
//			|| (str[i - 1] == 'R' && str[i] == 'P'))  
//		{
//			g[i] = g[i - 1];
//		}
//		else if (str[i - 1] == str[i])
//		{
//			g[i] = f[i - 1];
//		}
//		else 
//		{
//			g[i] = max(f[i - 1], g[i - 1]);
//		}
//	}
//	cout << max(f[n - 1], g[n - 1]) << endl;
//
//
//	return 0;
//}
//
//
//

#include<iostream>
using namespace std;
#include<vector>
#include<string>
#include<unordered_map>

#include<algorithm>
//int main() 
//{
//
//	int t = 0;
//	cin >> t;
//	while (t--) 
//	{
//		int n = 0;
//		string str;
//		cin >> n >> str;
//		unordered_map<char, int> mp;
//		for (auto e : str) mp[e]++;
//
//
//		int ret = 0;
//		ret += min(mp['A'], n);
//		ret += min(mp['B'], n);
//		ret += min(mp['C'], n);
//		ret += min(mp['D'], n);
//
//		cout << ret << endl;
//
//
//	}
//
//	
//
//	return 0;
//}




#include<iostream>
using namespace std;
#include<vector>
#include<string>
#include<unordered_map>

#include<algorithm>
//int main() 
//{
//	int t = 0;
//	cin >> t;
//	while (t--) 
//	{
//		string str;
//		cin >> str;
//		int ret = 0;
//		for (auto e : str) 
//		{
//			ret += (e - '0');
//		}
//		cout << ret << endl;
//	}
//	return 0;
//}
//
//
//
//
//



#include<iostream>
using namespace std;
#include<vector>
#include<string>
#include<unordered_map>

#include<algorithm>
//int main() 
//{
//	int t = 0;
//	cin >> t;
//	while (t--) 
//	{
//		int a1, a2, b1, b2;
//		cin >> a1 >> a2 >> b1 >> b2;
//		if (max(a1, a2) > max(b1, b2) && max(b1, b2) > min(a1, a2) && min(a1, a2) > min(b1, b2))
//		{
//			cout << 2 << endl;
//			continue;
//		}
//		else if (max(a1, a2) > max(b1, b2) && min(a1, a2) > max(b1, b2)) 
//		{
//			cout << 4 << endl;
//			continue;
//
//		}
//		else 
//		{
//			cout << 0 << endl;
//			continue;
//		}
//
//
//	}
//	return 0;
//}












//int main() 
//{
//	int n = 0;
//	cin >> n;
//	vector<int> arr(n);
//	unordered_map<int, int> index;
//	int mai = 0;
//	int smai = 1;
//	cin >> arr[0];
//	cin >> arr[1];
//	if (arr[0] > arr[1]) 
//	{
//		mai = 0;
//		smai = 1;
//	}
//	else 
//	{
//		mai = 1;
//		smai = 0;
//	}
//	for (int i = 2; i < n; i++) 
//	{
//		cin >> arr[i];
//		if (arr[mai] < arr[i]) 
//		{
//			smai = mai;
//			mai = i;
//		}
//		else if (arr[smai] < arr[i]) 
//		{
//			smai = i;
//		}
//	}
//	cout << smai + 1 << endl;
//
//
//	return 0;
//}







//
//int main() 
//{
//	int Y = 0;
//	cin >> Y;
//	
//	if ((Y % 4 == 0 && Y % 100 != 0) || (Y % 400 == 0))
//	{
//		cout << 366 << endl;
//	}
//	else cout << 365 << endl;
//
//
//	return 0;
//}


